Today's Tfhriursday 🌏🌎, time for our biweₐᵉkly quiz! 📊. Today: concrete complexity! More specifically: power and limits of DNF formulae to approximate Boolean functions.
— Clément Canonne (@ccanonne_) July 14, 2023
Fun fact: if you say "DNF formula" three times very fast, half your students disappear.
1/ pic.twitter.com/Fx7OjdEO6y
Answers and discussions for the last biweₐᵉkly quiz 📊 on concrete complexity: "DNFs is All You Need!" (Well, not quite. Or maybe very big ones.)
— Clément Canonne (@ccanonne_) July 30, 2023
Your goal: represent a Boolean function f: {0,1}ⁿ→{0,1} (messy object) using a DNF (structured object) https://t.co/l3OMuCo9p4
1/ pic.twitter.com/6vYr2umns6
📊 Today is Frhursday, and we're back for a (bi)weₐᵉkly quiz! Timely: you just met 2 witches 🧙♀️, and each gave you a bag of n distinct potions 🧪, each 🧪 labelled with a rune.
— Clément Canonne (@ccanonne_) June 1, 2023
Those potions? Some will make you larger, and some will make you small. And some, of course ...
1/ pic.twitter.com/sCet2hmPPi
(Long) overdue answer 🧵 for our last (bi)weₐᵉkly quiz on witches 🧙♀️, and how to foil them: efficient algorithms to decide if one can pick🧪 which cancel each other's effects ("do there exist numbers summing to zero?")
— Clément Canonne (@ccanonne_) June 29, 2023
And does randomization🎲 help?
1/ https://t.co/ixROedfbz0
📊 It's Friday here (and Thursday elsewhere for many: you know who you are!), time for a (bi)weₐᵉkly quiz!
— Clément Canonne (@ccanonne_) March 31, 2023
Today, let's do something simple, just to get our affairs in order: sorting!
1/ pic.twitter.com/rvdVUPuakA
Answers and discussion for last week's 📊(bi)weₐᵉkly quiz on sorting! "Given n numbers as input, sort those numbers."
— Clément Canonne (@ccanonne_) April 9, 2023
How hard can it be? What algorithm to use?
[Sorry for the delay, and keeping it short (I am a little under the weather).]
1/ https://t.co/iDnUb1n522
📊It's a bit late, but time for our (bi)weekly quiz! Today, a thing I probably* talked about before, but will almost certainly* come very handy at some point, even if it does look a bit random*.
— Clément Canonne (@ccanonne_) March 3, 2023
"Low-space Chebyshev!" 🎲 Or: randomness, but cheap.
* Bad puns, everywhere.
1/ pic.twitter.com/mZJfrx6doB
Oops. I never gave solutions for this one... a bit late, I guess, now? pic.twitter.com/cQDYUoUdWQ
— Clément Canonne (@ccanonne_) April 9, 2023
Today's 📊biweₑakly will be very short, more of a hook than a quiz. A 2-parter, on two different things!
— Clément Canonne (@ccanonne_) February 9, 2023
First one: Fibonacci. Recall that the Fibonacci numbers are defined recursively by F₀=F₁=1, and F(n+2)=F(n+1)+F(n).
Now, you can generalize that a little...
1/ pic.twitter.com/QKauphwgzP
Answers and discussion for last week's 📊biweₑakly quiz. Only two questions — let's dive in, first with computing Fibonacci-type numbers!
— Clément Canonne (@ccanonne_) February 15, 2023
How hard is it? I give you two initial values, and ask you to give me the n-th value of the sequence. Naively...
1/ https://t.co/eRP5KNd5do
📊It's Thurs-Fri-day [citation needed], time for a (bi)weekly quiz! It's been a while, so let's take it slowly... lest we make mistakes. Perfect segue: today, Online Learning Mistake Bounds!
— Clément Canonne (@ccanonne_) January 26, 2023
What?
Well, you want to learn a classifier, here a function f: {0,1}ⁿ→{0,1}...
`1/ pic.twitter.com/ovBW2BJBm3
📊 Answers and discussion for last week's quiz on online learning: mistake bounds, and where to get them!
— Clément Canonne (@ccanonne_) January 31, 2023
You want to learn some classifier f: {0,1}ⁿ→{0,1} given an (arbitrary) sequence of inputs. Making few mistakes *in total* over this sequence...
1/ https://t.co/M1YCGMkBFA
It's Friday! Or Thursday? It's the last 📊biweₑakly quiz of 2022! Today: how hard can it be to properly learn something?
— Clément Canonne (@ccanonne_) December 23, 2022
Recall the definition of PAC (Probably Approximately Correct) learning: you get labeled examples of the form <xₖ,yₖ>, where the data points xₖ are...
1/ pic.twitter.com/9G84SjJUIr
Answers and discussion for last week's 📊quiz on proper (PAC) learning. Upshot: sometimes #learning is easy... but not if you want to do it properly.
— Clément Canonne (@ccanonne_) December 26, 2022
I'll assume you've read the original 🧵 which recalls the def of the PAC (Probably Approximately Learning) framework. If not:
1/ https://t.co/pbVAYd2yz0
📊 It's Fri(Thurs)day, time for a biweekly quiz! With two questions today, on something very simple*: let's solve linear equations!
— Clément Canonne (@ccanonne_) December 8, 2022
So you have n variables, x₁, x₂, ..., xₙ and a prime p, and are given a set of linear equations over them, each modulo p.
*[citation needed]
1/ pic.twitter.com/5qLbpVL9y1
Answers and discussion for last week's 📊 quiz on solving linear equations (or, at least, some complexity aspects of it).
— Clément Canonne (@ccanonne_) December 12, 2022
Or, as computational complexity theorists might call it: "The Most Dangerous (Unique) Game."
(Alright, they might not.)
1/ https://t.co/sMHyp1zUis
It's Friday, time for a (bi)weₐᵉkly quiz! 📊 Today, since it's summer here, and it's sunny, and there are waves... let's go surfing. 🏄♀️
— Clément Canonne (@ccanonne_) November 24, 2022
But you cannot surf without a surfboard, right? Should you buy one? Or should you rent?
[And should you go to Bondi or Dee Why?]
1/ pic.twitter.com/0NqVrHNYld
Quite overdue, so here we go: a short 🧵 of answers and a bit of discussion for last week's quiz on surf rental, and online algorithms!
— Clément Canonne (@ccanonne_) November 30, 2022
What's an "online" algo? It's one whose input comes as a sequence, one thing at a time, w/ typically no assumption..
1/ https://t.co/qhEKU5bLLW
Thursfriday is here, time for a (bi)weækly quiz! 📊 Let's talk about what happens when we take big things and turn them into small things without making big things that were far become small things that are close and vice versa.
— Clément Canonne (@ccanonne_) November 11, 2022
Alright, let's talk dimensionality reduction.
1/ pic.twitter.com/BbIEphw58V
Welcome to Monday!* The sun is shining, the random Gaussian matrices are chirping in the low-dimensional trees... answers and discussion for last week's quiz 📊 on dimensionality reduction!
— Clément Canonne (@ccanonne_) November 14, 2022
Recall: n vectors in a d-dim Euclidean space...
* I swear! https://t.co/LD3A468Nve
1/
It's Friday—maybe Thursday: time to plant a 📊 (bi)weₑakly quiz!
— Clément Canonne (@ccanonne_) October 28, 2022
Today, we hide stuff in graphs: planted cliques! Take a random graph on n nodes by adding each edge, independently, with proba 1/2. In fancy terms: take G~G(n,1/2) according to the Erdős–Rényi(–Gilbert) model.
1/ pic.twitter.com/tlYiYEEDUv
A (quick) answer thread for last week's weₑakly quiz 📊 on planted clique: first, the name Erdős–Rényi–Gilbert. You may know random G(n,p) graphs as the Erdős–Rényi model of random graph: n nodes, include each of the n choose 2 edges independently...
— Clément Canonne (@ccanonne_) October 31, 2022
1/ https://t.co/Kgs4tRHwtR
Today's quiz-day! 📊A short one, on stuff I may have mentioned before: the importance of assumptions! Discrete proba distributions! Hope you won't find it too... monotone.
— Clément Canonne (@ccanonne_) September 30, 2022
A distribution on [n] := {1,2,...,n} is monotone if its probability mass function is non-increasing.
1/4 pic.twitter.com/RMdxwjr8eR
📊Answers and discussion for last week's quiz on the impact of assumptions in testing and learning distributions.
— Clément Canonne (@ccanonne_) October 3, 2022
You have i.i.d. samples from some probability distribution p on [n] := {1,2,...,n}, and, well, want to learn/test *something* about it...
1/ https://t.co/BGXXsLjkOv
Guess what? It's Frithursday, time for a quiz! 📊 Today, "the fundamental limitations of deep learning."
— Clément Canonne (@ccanonne_) September 15, 2022
Just kidding: constant-depth Boolean circuits, and what they can(not) compute!
1/ pic.twitter.com/z4i8qXL4BO
📊Answers and discussion for last week's quiz on lower bounds for small-depth circuits: "What can we compute with reasonable-size circuits?"
— Clément Canonne (@ccanonne_) September 18, 2022
A short thread on "concrete complexity" and "circuit complexity."
1/ https://t.co/21ZIJBWN9B
It's Frithursday, time for a quiz!🧩 Today, let's see what happens when the Eastern Roman Empire go full Bernoulli.
— Clément Canonne (@ccanonne_) September 1, 2022
Ah, sorry. I meant Byzantine coin flipping. n people, each sends one (randomized) message, the goal is to aggregate those n bits into 1 random coin toss. BUT..
1/ pic.twitter.com/3lQszFSgGK
Answers and discussion for last week's quiz🧩 on distributed coin flipping: "can people collectively generate a coin flip even when some of them adversarially try to skew the result?"
— Clément Canonne (@ccanonne_) September 5, 2022
We had 3 questions, based on how we model the 'adversary' who controls the malicious people.
1/ https://t.co/aZy158pT8A
Oh my, Friday already (Thursday? You know where you are). Time for our (bi)wᵉₐe quiz! 🧩
— Clément Canonne (@ccanonne_) August 18, 2022
Today, we play cards. There are n pairs of cards, face down on the table. Each pair has a unique picture on it (so 2n cards, n distinct pictures in total), but the cards are shuffled.
1/ pic.twitter.com/XSjaCqfCJP
Alright, here we go—answers and discussion for last week's quiz on Memory, Time, and "Concentration." My apologies for the delay!
— Clément Canonne (@ccanonne_) August 24, 2022
So you have 2n cards: n pairs, where each pair has a unique picture (say, a 🦏 on both, or a 🦍). The 2n cards are face down, shuffled on a table.
1/ https://t.co/nLWXgq7n1i
🧩 It's Friday! Thursday! Maybe! Time for a quiz. Often, in an argument or a proof, there is *that* magic step which simplifies everything by invoking a useful|cute|eldritch bound out of nowhere. Let's see a few of those convenient inequalities...
— Clément Canonne (@ccanonne_) August 4, 2022
Let's compare things!
1/ pic.twitter.com/e5NnTUevy3
🧩 Answers and discussions for last week's quiz on (some) inequalities, and hopefully a teaser for many others you may find useful.
— Clément Canonne (@ccanonne_) August 8, 2022
Today's menu: union 🧅 bound (and a partial converse), Bernoulli's inequality (but which Bernoulli?), Abel's, and Chebyshev's (not that one!).
1/ https://t.co/b1rC3jM7XB
🧩 It's Friday! Time for a quiz! Today, a "simple" one, about very "basic" results, with all the caveats that "quotes" imply.
— Clément Canonne (@ccanonne_) July 15, 2022
Polynomials! How do they work, and what are they good for?
1/6 pic.twitter.com/xgKbk4udrX
Answers and discussion for last week's quiz on polynomials: 3 Properties Big Algebra Doesn't Want You To Know.
— Clément Canonne (@ccanonne_) July 19, 2022
So you have a field 𝔽, and an n-variate polynomial P(X₁,...,Xₙ) of total degree d over 𝔽 (the sum of degrees of all variables, in every monomial, is at most d).
1/ https://t.co/fHdJmahs6L
It's been a while, but I'm back, it's sort-of-Thursday-Friday: time for a weᵃₑkly quiz! 🧩
— Clément Canonne (@ccanonne_) July 1, 2022
Today: probability amplification! (Or: how to go from something that is sometimes good to something that's almost always good)
1/ pic.twitter.com/nf9dfuAc43
🧵Answers and discussion for last week's quiz on probability amplification: you have an algorithm A which, on input x, "costs" 🪙(x) and outputs a solution 🎁(x) which is "good" (belongs to a "good set" 🎉(x)) with probability 51%.
— Clément Canonne (@ccanonne_) July 5, 2022
You would like 1-δ, not 51%. How?
1/ https://t.co/mcZ3ivJxh2
📊 It's Friday-here, time for a biweekly quiz! Today: not-quite- #quantum computing. Quantum computation obeys a few rules. Unitary transformations, measurements with probability proportional to squared norm of amplitudes, collapse... Rules!
— Clément Canonne (@ccanonne_) April 28, 2022
What breaks when you change them?
1/ pic.twitter.com/kmBNRENqe1
📊 Answers and discussions for last week's talk about changing the rules of quantum computing. I will only briefly give the answers, and point to some papers (in particular, one) if you want more details.
— Clément Canonne (@ccanonne_) May 2, 2022
tl;dr: things — they break.
1/ https://t.co/4KmR0KXfQb
📊 It's Thursday-or-so, time for a (bi)weekly quiz! Yes, it's back. As promised, with "SQ Learning"!
— Clément Canonne (@ccanonne_) April 14, 2022
What is that, you ask? Good question. Here 'SQ' stands for "Statistical Query," which is a technical way of saying "we'll try and weaken our algorithms, see what happens."
1/ pic.twitter.com/l3kdv5joZa
📊Answers and (brief) discussion for this week's quiz on SQ learning! I'll keep it short, but by all means feel free to ask for pointers, references, or questions-actually-more-of-a-comment-than-a-question at the end of the 🧵!
— Clément Canonne (@ccanonne_) April 17, 2022
1/ https://t.co/DAKaNJ1GpU
📊 It's Thursday|Friday, time for a short quiz! SAT, but not the controversial one.
— Clément Canonne (@ccanonne_) March 3, 2022
I give you a CNF and ask you to give me a satisfying assignment. Let's actually say I give you a 3-CNF, where each clause has exactly 3 variables:
(∨∨)∧...∧(∨∨)
Well, that's NP-complete.
1/ pic.twitter.com/5vbFWteCb1
📊 Answers and discussion for last week's quiz on MAX-SAT: "how many clauses of a 3-CNF formula can you satisfy in polynomial time before Big NP-Hardness comes at you?"
— Clément Canonne (@ccanonne_) March 6, 2022
Input: a CNF on n Boolean variables with (exactly) 3 variables per clause, and m clauses.
1/ https://t.co/lzJ2jqyfPG
📊 It's Friday,* time for our (bi)weekly quiz! Today, a foray into computational geometry (our a little bit of it)! Let's start as all good stories start: you have a set V of n points living on the plane, i.e., V ⊆ ℝ².
— Clément Canonne (@ccanonne_) February 17, 2022
*I swear. Come here and you'll see 🌏
1/ pic.twitter.com/AJMikm1iCv
📊 Answers and discussions for last week's quiz on computational geometry and spanners. "Spanners: distance computations are so edgy!"
— Clément Canonne (@ccanonne_) February 20, 2022
So: you have a set V of n points in the plane, defining a complete graph G whose edges are weighted by the Euclidean) distances b/w points.
1/ https://t.co/Xf3LxIIuKJ
📊 It's Friday (Thursday for some of you at home), time for a very short, very open quiz!
— Clément Canonne (@ccanonne_) February 3, 2022
Two questions, about weird functions, and where to find them. Time complexities, or other: you decide.
1/3 pic.twitter.com/hR7WEYGg4H
📊 Answers and discussion for last week's brief quiz on monsters: things that pop up in computer science and analysis/computational complexity, but shouldn't, no they shouldn't, please make it stop.
— Clément Canonne (@ccanonne_) February 6, 2022
1/ https://t.co/rBj6nvUyC8
📊 Alright, it's 2022, it's Frithursday (Thriday?), time to resume the fortnightly quizzes!
— Clément Canonne (@ccanonne_) January 20, 2022
I'm going to go out of my depth here and talk about quantum stuff. Testing data, but Quantumly. Hopefully, that won't be a superposition of all the mistakes I could make.
1/ pic.twitter.com/0dpg7ee4nj
📊 Answers and discussion for (1/√2)(|this⟩+|last⟩) week's quiz on #quantum mixedness testing: tasting your quantum 🥗!
— Clément Canonne (@ccanonne_) January 23, 2022
Some terminology first: we're given a known k-dimensional quantum state σ (σ stands for "σalad," k for "kaesar"), and n copies of an unknown state ρ...
1/ https://t.co/5Mq6dfqDs3
📊 It's Thursday, time of a quiz! Today, no randomness, just good ol' deterministic algorithms (and a little linear algebra not-so-hidden in the middle).
— Clément Canonne (@ccanonne_) December 16, 2021
So, you have a graph G on n vertices (n is even). You're interested in pairing the nodes: i.e., perfect matchings.
1/ pic.twitter.com/3NXsqDX8TM
📊 Answers and (short) discussion for last week's quiz on... matchings, and where to find them (and how to count 'em).
— Clément Canonne (@ccanonne_) December 20, 2021
Recall that a matching M ⊆ E is a list of vertex-disjoint edges from a graph G=(V,E). It is perfect if |M|=|V|/2.
1/ https://t.co/bG1MvE0z6O
📊 Friday here, Thursday there, time for a quiz! The wait is over: now, we weigh. ⚖️
— Clément Canonne (@ccanonne_) November 25, 2021
You've been given n indistinguishable (to the eye) potatoes. It is very important to you that they all are identical, and in particular all have the same weight.
Do they though?
1/
📊 Answers and discussions for this [last] week's quiz on potatoes! Sorry for the delay: the weight is over.
— Clément Canonne (@ccanonne_) November 29, 2021
So you have 🥔s, indistinguishable to the eye, and want to make sure the seller didn't lie to you when he claimed they all weighed the same. https://t.co/jbXyAkIfzC
1/
📊 It's Thursday! Or Friday. Who knows anymore, and what is time? In any case, it's quizday! 🧩
— Clément Canonne (@ccanonne_) November 11, 2021
Today, some communication complexity. You might know the drill: Alice has input x, Bob has input y, they both know some function f and want to compute f(x,y). But talking is hard.
1/ pic.twitter.com/WSscKU8u8r
📊 Answers and discussion for this week's quiz on communication complexity: Alice has x, Bob has y and wants to compute f(x,y) correctly with proba ≥ ¾.
— Clément Canonne (@ccanonne_) November 14, 2021
They both know f ahead of time, but Alice can only send a few bits to Bob (pigeons ain't cheap!).
1/ https://t.co/vIE0VK78Ss
📊 It's Thursday (for me), I have a coffee, time for a weekly quiz!
— Clément Canonne (@ccanonne_) October 27, 2021
Today: Boolean circuits, functions, and functions which require large circuits.
1/ pic.twitter.com/J8Vpzg2XZm
📊 Answers and (short) discussion for this week's quiz on circuits, and how large they must be to implement some Boolean functions. https://t.co/xtHYGRwLpB
— Clément Canonne (@ccanonne_) October 30, 2021
1/
📊 Since couplings have been on my mind lately, here is a very short, two-parter weₐᵉkly quiz.
— Clément Canonne (@ccanonne_) October 14, 2021
Let's start with a fun suspect. We have n, and n goes to infinity. We have pₙ, pₙ goes to 0. And we have λ, npₙ goes to λ.
Now, let's look at Xₙ~Binomial(n, pₙ)...
1/6 pic.twitter.com/xq2HnD8ld4
📊 (A bit overdue) answers and discussions for this week's quiz on Poisson v. Binomial, and stochastic dominance.
— Clément Canonne (@ccanonne_) October 17, 2021
In which we look at Xₙ~Binomial(n, pₙ) where npₙ → λ as n→∞, Y~Poisson(λ), and try to compare them.
1/ https://t.co/ODaLzmGwCN
📊 It's Friday here, still Thursday for many: time for our weekly quiz! Today: triangles ◁ △ ▷▽. In graphs! "Are there any?"
— Clément Canonne (@ccanonne_) October 7, 2021
So, what's a △ in an (undirected) graph? A graph G=(V,E) on |V|=n vertices has a △ b/w vertices i,j,k if (i,j),(j,k),(i,k)∈E (all 3 are edges).
1/ pic.twitter.com/XMHpRgJHOk
📊 (Brief) answer thread for this week's quiz on triangle ◁ △ ▷▽ detection in undirected graphs: or "we can do this incredibly fast! But it's incredibly slow."
— Clément Canonne (@ccanonne_) October 9, 2021
1/ https://t.co/pTcPTYBBIP
📊 It's Thurfriday, time for our weekly quiz! Today, some probability puzzles: collisions!
— Clément Canonne (@ccanonne_) September 23, 2021
There is an unknown probability distribution over {1,2,....,n}. You get to do the usual stuff: ask for independent samples. If you see the same value several times: collision, you win!
1/ pic.twitter.com/rq3LTmI8Ix
📊 Answers and discussion for this week's quiz on collisions: or, "how to best win cookies🍪 by playing weird random games."
— Clément Canonne (@ccanonne_) September 25, 2021
Recall: unknown probability distribution over {1,...,n}. A "t-way collision" among samples is if you see some value t times.
1/ https://t.co/84sTNaMWMv
📊 It's Thursday! Time for our (weakly) weekly quiz on theoretical computer science (TCS), random nuggets of random things, and—this week, and this week only!—pacts with the devil.
— Clément Canonne (@ccanonne_) September 9, 2021
Because sometimes, you *really* want to solve those decision problems, don't you?
1/ pic.twitter.com/GsgBzQNl97
📊 Answers and discussion for this week's quiz on interactive proofs. Interactive proofs: when things are hard, talk to a fiend! 😈 https://t.co/gVCDMvZ4UK
— Clément Canonne (@ccanonne_) September 12, 2021
1/15
📊 It's Thursday, time for a short weekly quiz! About a very basic problem: adding numbers.
— Clément Canonne (@ccanonne_) August 26, 2021
Yes, counting. How hard can that be?
1/ pic.twitter.com/LNWB9jHLfF
📊 Answers and discussion for this week's quiz on addition and circuit complexity. Addition: do something that counts!
— Clément Canonne (@ccanonne_) August 28, 2021
So the inputs are two n-bit integers x,y, your goal is to output x+y. No trick, no catch, just build a Boolean circuit for that... https://t.co/OsdhdwYWzP
1/
📊 It's Thursday (it is!), time for a wₑeᵃkly quiz! A short one: let's not be greedy.
— Clément Canonne (@ccanonne_) August 19, 2021
Yeah, let's not be greedy. Let's leave that to the algorithms! 🤖
1/ pic.twitter.com/n1OdVbWgQ2
📊 Answers and discussions for this week's we(a)ekly quiz on greedy algorithms.
— Clément Canonne (@ccanonne_) August 22, 2021
Remember: greedy's only a sin if you *forget* to try it!
1/ https://t.co/kK270ve3e6
📊 It's Thursday for some, time for a weekly quiz! This Frirsday, 3 questions on a topic I touched upon a few times already: ways to measure distances between probability distributions.
— Clément Canonne (@ccanonne_) July 29, 2021
(Good ways, and bad ways.)
1/ pic.twitter.com/DnMXrD0cPy
📊 Answers and discussions for this week's quiz on "distances between probability distributions." Or "how do I measure those things in a sensible way?"
— Clément Canonne (@ccanonne_) August 1, 2021
First caveat: there are *many* other distances I will not discuss. For references or questions, please comment at the end!
1/ https://t.co/XzZiwqRIBC
📊 It's Frursday*, time for a weekly quiz! Let's play a game, involving balls, and bins, and you throwing them.
— Clément Canonne (@ccanonne_) July 15, 2021
So you have m balls, and n little cute baskets of equal size, all woven by hand in the most delicate and artisanal fashion, henceforth called "bins."
*Time zones.
1/ pic.twitter.com/SorYYEbhBN
📊 Answers and discussion for this week's quiz on balls ⚾, baskets 🧺, and who's going to pay for those now that you've thrown stuff in them and they're all damaged, uh?
— Clément Canonne (@ccanonne_) July 18, 2021
I have to admit, you've been quite good on this quiz. Maybe I should up my game.
1/ https://t.co/QKFkdvUa6Z
📊 It's Friday/Thursday, depending on where you are: time for a (weakly) weekly quiz! This week: a (tiny glimpse) at lattice-based cryptography.
— Clément Canonne (@ccanonne_) July 8, 2021
I'm not a specialist, so if I make any mistakes... we'll just call that "learning with errors"?
1/ pic.twitter.com/fZqVluiAcO
📊 Answers and discussion for last week's quiz on lattice-based crypto. I won't go into much detail; to know more, check out the links at the end of the thread.
— Clément Canonne (@ccanonne_) July 12, 2021
1/ https://t.co/QsarURu21c
📊 It's Thursday! Hope you're all staying safe. As promised, today's weekly quiz is #STOC21 (and, generally, broad-TCS) related.
— Clément Canonne (@ccanonne_) June 24, 2021
[I used those questions in the STOC (first) trivia on Tuesday, so if you were there... like every non-trivial graph, you have an edge.]
1/ pic.twitter.com/Cfp8w8rHm5
📊 Answers and discussion for this week's quiz on (some aspects of) the history of Theoretical Computer Science, that is, TCS Factoids.
— Clément Canonne (@ccanonne_) June 26, 2021
1/ https://t.co/M4l3roK0ND
📊 It's Friday here, and Thursday there, and possibly in-between somewhere: time for a weekly quiz! Today, let's count stuff. Boolean functions.
— Clément Canonne (@ccanonne_) June 10, 2021
Fixing n (it's big!), we consider functions of the form f: {0,1}ⁿ→{0,1}, i.e., things that take n bits and output one.
1/ pic.twitter.com/Aev6yEbEDX
📊 Belated answers and discussion for last week's quiz on "how many of those Boolean functions are there?"
— Clément Canonne (@ccanonne_) June 15, 2021
Before we start, let's give a motivation why counting those things might be important... there are others, of course ("how many bits to index" and "it's fun" being two).
1/ https://t.co/jesFJAYQU4
📊 It's Thursday for many, time for a weekly quiz! I promised a thread on anticoncentration last week, so let's first wonder what that can be. A type of small rodent, maybe?
— Clément Canonne (@ccanonne_) May 20, 2021
[Spoiler: not a type of small rodents.]
1/ pic.twitter.com/ke6V4pIwld
📊 Answers and discussion for this week's quiz on streaming and moment estimation.
— Clément Canonne (@ccanonne_) May 24, 2021
I am currently overwhelmed by deadlines, so I prepared a pdf for the answer (see at the end of the thread), and in this thread will just talk. a. lot. 🗣️
1/ https://t.co/YFoIHgH5xX
📊 It's Thursday [in many places], time for a weₐᵉkly quiz! As promised, this one's on #streaming . You know, Netflix, HBO?
— Clément Canonne (@ccanonne_) May 13, 2021
Good. Not that.
1/ pic.twitter.com/bgQSktuXmr
📊 Answers and discussion for this week's quiz on streaming and moment estimation.
— Clément Canonne (@ccanonne_) May 15, 2021
Reminder: a sequence of m=n elements a₁,..,aₘ from a universe [n]={1,..,n} arrive sequentially in an arbitrary order. You don't have enough memory to store all of it.
1/ https://t.co/ry9ZE9d4pj pic.twitter.com/krJZf1cx6n
📊 It's Thursday-somewhere-Friday-here, time for a wᵉₐkly quiz. Today, 4 questions on communication!
— Clément Canonne (@ccanonne_) April 29, 2021
Say hi to 👩💻 Alice and Bob 👨💻. They have something to figure out, but they'd rather not talk much about it.
1/ pic.twitter.com/NQskyRspnv
📊 Answers and discussion for this week's quiz on communication complexity with various types of shared randomness.
— Clément Canonne (@ccanonne_) May 1, 2021
Remember: we have 👩💻 Alice, and 👨💻 Bob. They don't talk to each other anymore. But they'd still like to work out something together.
1/ https://t.co/K57jkzY8Rk
📊 It's Thursday, time for a weekly quiz! We're on Twitter. Twitter is a social network. Social networks are basically graphs (with gifs).
— Clément Canonne (@ccanonne_) April 22, 2021
Let's look at graphs (without gifs). But with gifs.
1/ pic.twitter.com/W44pjv7m7c
📊 Answers and discussion for this week's quiz on graphs, cliques, and hardness of Max-Clique. "The answers may surprise you!"
— Clément Canonne (@ccanonne_) April 24, 2021
(Yes, that was a clique-bait.)
1/ https://t.co/T6QOiUvur3
📊 So, here is the answer, some discussion, and more questions about that
— Clément Canonne (@ccanonne_) April 9, 2021
"If Z=X+Y is Binomial, what about X,Y?"
question. (So, I lied: here's a pop quiz!)
Warning: answers in two or three days.
1/9 https://t.co/x7X0mssW4q
📊 Short thread: answers and proofs for the 3 extra questions on independent X,Y such that X+Y is Binomial.
— Clément Canonne (@ccanonne_) April 11, 2021
We previously saw that if we assumed X,Y and integer-valued, then X and Y had to be Binomial themselves.
But what if we don't assume that? https://t.co/r5sQbhiFKT
1/ pic.twitter.com/5AYlfLT9vF
📊 It's Thursday (and has been for a while, here in the Future 🌏), time for a weekly quiz! Since it's April 1st, and I'm French, this will be about Fish. 🐠 https://t.co/dihjvbYiN3
— Clément Canonne (@ccanonne_) April 1, 2021
Sorry: about Poissons, which are *random* fish.
1/6 pic.twitter.com/v5hnn8XeOv
📊 After a long delay due to a long weekend: answers and discussion for last week's quiz on Poisson things.
— Clément Canonne (@ccanonne_) April 6, 2021
First, to explain the 🐠: "Poisson" was the name of Siméon-Denis Poisson, French mathematician and physicist . It also means "Fish." Tough.
1/ https://t.co/sZ9XysH6jf
📊 It's Thursday (it is!), time for a weekly quiz. This week's will be short (4 questions), and about a "basic" question: how to distinguish between two biased coins. 🪙
— Clément Canonne (@ccanonne_) March 25, 2021
Formally, I give you a coin and a value p, and promise you it lands "heads" with proba either p or p+ε..
1/
📊 Answers and discussions for this week's thread on distinguishing biased coins 🪙. Coin: it's like a die 🎲, but with two sides.
— Clément Canonne (@ccanonne_) March 27, 2021
So the goal is, given a 🪙, to distinguish b/w it landing Heads w/ probability p or >p+ε, with as few flips as possible. https://t.co/xMOmGACHVD
1/
📊 It's Thursday, time for a weekly quiz! Today, you're dropped in a labyrinth, and can't remember much: will you be able to get out?
— Clément Canonne (@ccanonne_) March 18, 2021
[In complexity terms: it's about L, NL, and SL. The labyrinth stuff is much catchier.]
1/ pic.twitter.com/jiDb9uD6Gy
📊 Answers and discussions for this week's quiz: "how to get out of a maze when you have a really bad memory."
— Clément Canonne (@ccanonne_) March 20, 2021
G=(V,E) is a graph (directed or undirected) on n nodes. You're dropped at a source node s, want to know if there is a path to the exit t.
1/ https://t.co/KXiMRQF7lY
📊 It's still Thursday! Time for a weekly quiz. On polling, deniability, and coffee.
— Clément Canonne (@ccanonne_) March 12, 2021
The year is 2027. Coffee production has dwindled, due to the effect of climate change on crops. Yet coffee consumption has skyrocketed, after it was noticed that caffeine can power computers.
1/
Answers and discussion for this week's quiz on coffee consumption, polling, privacy, and why we can't seem to find enough caffeine to power our java-hungry ML models 🤖 these days.
— Clément Canonne (@ccanonne_) March 14, 2021
1/ https://t.co/b1Vbt1WlBI pic.twitter.com/SMM6Cy1Irs
📊 It's Thursday here (I swear), time for a quiz! Let's talk about decisions, how hard they are to make, and the power of asking a friend.
— Clément Canonne (@ccanonne_) March 4, 2021
That is, it'll be about oracle machines and complexity classes.
1/ pic.twitter.com/rY3PsdNuVO
📊 Answers and discussion for this week's quiz on complexity classes and "oracle machines"!
— Clément Canonne (@ccanonne_) March 6, 2021
Before starting: if you're interested in computational complexity and are not already, follow @BooleanAnalysis , @rrwilliams , and @IgorCarboniOliv .
1/ https://t.co/XPl94x1w6S
📊 It's Friday morning here (and Thursday in many other places, I'm told): time for a weekly quiz!
— Clément Canonne (@ccanonne_) February 18, 2021
Today: "the definition of differential #privacy , why"? (Also, "what's an f-divergence"?)
I'm not going to go through the reasons to introduce differential privacy...
1/ pic.twitter.com/gLWlIDRqJm
Answers and discussion for this week's quiz on differential #privacy . So, you have a dataset D of n records (private info!), and want to run an algo A on it.. and publish the result *while preserving privacy.*
— Clément Canonne (@ccanonne_) February 21, 2021
The question is, what could that mean?
1/ https://t.co/nr7wLaXUvt
📊 It's Thursday-somewhere-and-Friday here, time for a weekly quiz! Let's look into a 'fun' algorithmic problem with numbers and arrays . A type of zero-sum game ➕, if you will. (It's not, really.)
— Clément Canonne (@ccanonne_) February 11, 2021
So you're given as input an array A of n numbers (weird gift, but why not).
1/
📊 Answers and discussion for this week's quiz on 3SUM: given an array A of n numbers, is there some i,j,k such that A[i]+A[j]+A[k]=0?
— Clément Canonne (@ccanonne_) February 14, 2021
To keep things simple, we're going to assume the numbers are integers & that we can add, subtract, etc. in time O(1).
1/ https://t.co/JJ1QS7EzHG
📊 It's Thursday (i.e., Friday 🇦🇺), it's been a while, and it's an installment of our (weakly) weekly quiz.
— Clément Canonne (@ccanonne_) February 4, 2021
It's the ICML deadline for many, though, so let's temper our expectations and only have *checks* 4 questions. Also, X is a discrete random variable on a domain D⊆ℝ.
1/8
Answers and discussion for this week's quiz on "do expectations and variances even exist? Does anything even exist? Wooow. 🤯"
— Clément Canonne (@ccanonne_) February 7, 2021
So, X is a random variable on a domain D⊆ℝ (I wrote "discrete," that was an unfortunate typo—it'll depend)
1/ https://t.co/v1K8tEeDv6
📊 Guess what: it's Thursday! Time for a (weakly) weekly quiz. This one may remind some of you of your randomized algorithms class🎲
— Clément Canonne (@ccanonne_) January 14, 2021
"What to expect when we just do random stuff?"
1/ pic.twitter.com/p3ZWJOuLmL
📊 Answers and discussions for this week's quiz on "doing random stuff and expecting things"
— Clément Canonne (@ccanonne_) January 17, 2021
The upshot: random choices 🎲 can lead to surprising insights, even if you don't care for randomized algorithms! (Now, combinatorists may argue that...
1/ https://t.co/7W46AcOuge
📊 It's Thursday, and a lot has been happening in (some parts of) the world... a lot to (un)pack or cover, so let's do none of that: here is a weekly (albeit weakly) quiz instead.
— Clément Canonne (@ccanonne_) January 7, 2021
Covering, packing, and ε-nets. Let's have a ball!
1/9 pic.twitter.com/cSahgJMsGN
📊 Answers and discussion for this week's quiz: on covering, packing, and the importance of norms.
— Clément Canonne (@ccanonne_) January 9, 2021
Below, unless specified otherwise (X, ‖.‖) is a normed space (metric space suffices up to Q4), Θ⊆X, and ε>0. Think of X=ℝⁿ for n≫1 for "intuition."
1/ https://t.co/qjW45MC6rD
📊 It's Thursday, time for a weₐᵉkly quiz! A two-parter, ft. Quantum Santa: merry Christmas, wherever you are!
— Clément Canonne (@ccanonne_) December 24, 2020
Obviously, there are many children on Earth, namely n>>1. Some have been naughty, some have been nice: Christmas Alice 🤶 and Christmas Bob 🎅 are keeping track.
1/ pic.twitter.com/pPHKSBMCZX
📊 Answers and discussions for this week's quiz on the communication complexity of |naughty∩nice|! 🤶
— Clément Canonne (@ccanonne_) December 26, 2020
I hope you had, whether you celebrate Christmas or not, a relaxing break with family or friends, and wish you more of those times to come.
1/8 https://t.co/CJw5GCPuBr
📊 It is, if I am not mistaken, Thursday (in several parts of the world at least): time for a (weakly) weekly quiz!
— Clément Canonne (@ccanonne_) December 17, 2020
It's been a hard year, month, and week. Let's figure out what *else* is (computationally) really hard.
1/9 pic.twitter.com/sihNkomUWR
📊 Answers and discussion for yesterday's quiz on NP-Hardness of various things (or lack thereof).
— Clément Canonne (@ccanonne_) December 18, 2020
Since I forgot to mention it yesterday, all graphs considered were undirected. Hopefully that didn't mislead anyone...
1/ https://t.co/J9n6tcw5DF
📊 It's Thursday, time for our weekly (but weakly so) quiz! This week: integers, and remarkable sequences.
— Clément Canonne (@ccanonne_) December 3, 2020
See this as an extended ad for the OEIS, if you will. Also, if you don't know the OEIS: go check it out (and come back)! https://t.co/CFzSxQu4Wy
1/ pic.twitter.com/QB8tpCA8pC
📊 Answers and discussion for yesterday's quiz on sequences (and their names).
— Clément Canonne (@ccanonne_) December 4, 2020
Before we go to the first question, again: if you haven't, bookmark https://t.co/DVdLWdI3UT . It's useful: the solution to some of your problems may be recorded there!
1/ https://t.co/gN1xUHjmZb
📊 It's Thursday, it's Thanksgiving, and it's time for a (weakly) weekly quiz!
— Clément Canonne (@ccanonne_) November 26, 2020
Let's play a game. I'll write sentences: some of them refer to actual results (from math or computer science). Some of them are lyrics, random quotes (or nothing). Can you find which is which?
1/8
📊 Answers and discussion for yesterday's Thanksquizzing 🦃: "theorem or random string of words?"
— Clément Canonne (@ccanonne_) November 27, 2020
tl;dr: theorem, not theorem, theorem, theorem, not a theorem, theorem.
1/ https://t.co/mU516LZIt1
📊 Thursday morning:* time for a weekly quiz! Let's talk about... POT!
— Clément Canonne (@ccanonne_) November 12, 2020
Testing of functions, graphs, etc. (in all generality) says you have an input thing f: X → Y, want to test whether f has some property 𝒫 (i.e., f∊𝒫) or is "far" from it (d(f,g)>ε for all g∊𝒫). How?
1/7 pic.twitter.com/MW04TnR027
📊 Answers and discussions for Thursday's quiz! Let's look at the answers for those distinctions between (property) testing algorithms.
— Clément Canonne (@ccanonne_) November 14, 2020
Quick recap: given a 'property' 𝒫 (subset of functions) and some access to some function f, accept if f∊𝒫.
1/12 https://t.co/8UmRqPGYAe
📊 It's Thursday, and with it another weekly quiz! Since there is a lot going on these days, I'll keep it very short.
— Clément Canonne (@ccanonne_) November 5, 2020
Today: Fibonacci numbers, and adding a little random kick to them. (Also, here's a cute animal if you need a break from the news.)
1/5 pic.twitter.com/DOuCtmeAAZ
📊 Answers and discussion for yesterday's short quiz on the Fibonacci sequence and a random variant 🎲.
— Clément Canonne (@ccanonne_) November 6, 2020
Let's first recall what the Fibonacci numbers are: we won't go through the whole "rabbits are breeding" thing, but it goes as F(n)=F(n-1)+F(n-2)...
1/ https://t.co/Ofybr88jO7
📊 Thursday! Time for an instance of our weekly (but weakly so) quiz.
— Clément Canonne (@ccanonne_) October 29, 2020
Let's talk about prime numbers! You know, those things really useful in number theory, Amazon orders, and cryptography.
So you want to find a prime, and it needs to be n-bit long, and it can't be 57.
1/ pic.twitter.com/cish0qZRBS
📊Answers and discussion for yesterday's quiz on prime numbers! The gist of the quiz was:
— Clément Canonne (@ccanonne_) October 30, 2020
"Given n, can we efficiently find an n-bit prime number? Can we do that deterministically? In a randomized way? What about 'pseudo-deterministically'?"
1/ https://t.co/ie8cmGuDyl
📊 Sorry for the delay—here is today's (weakly) weekly quiz. It'll be ≈ brief: our goal is to have a superficial look at some of the (mathematical) inequalities we face on a daily basis.
— Clément Canonne (@ccanonne_) October 22, 2020
Some will be true, some false, and some will look like they could go both way.
1/8 pic.twitter.com/qMNcBIZ8h8
📊 Answers and discussion for this week's quiz on inequalities between norms.
— Clément Canonne (@ccanonne_) October 24, 2020
First, let's recap notation. As noted by some, one could unify the notation by seeing both as Lp norms under a suitable (e.g., counting) gen'l measure, (∫|x|ᵖω(dx))^{1/p}.
1/ https://t.co/ci5Cuxp80n pic.twitter.com/bWtrEll4Y8
📊 It's that day of the week: time for a we(a|e)kly quiz! Today's quiz will be loosely based on a problem from a learning theory course I took back in the days, when dinosaurs roamed in Manhattan; and involves balloons🎈.
— Clément Canonne (@ccanonne_) October 8, 2020
Specifically: when do they pop?
1/9 pic.twitter.com/Xd9TxZYUgW
📊 Answers and discussion for yesterday's "pop quiz" on balloons🎈, and #learning .
— Clément Canonne (@ccanonne_) October 9, 2020
Recall the setup: you have a very small number of state-of-the-art 🎈. They pop at some unknown height N* (in "footmeters") , an integer b/w 1 and N. Your goal is to learn (exactly) this N*.
1/ https://t.co/p9PrALexWl
📊 It's that time of the week: Thursday, unless I've been fooled again. Time for a quiz! Today, we'll deal with something quite "basic:" sorted numbers, and how to check that.
— Clément Canonne (@ccanonne_) October 1, 2020
As people said to Louis XVI: "let's keep it short."
1/11 pic.twitter.com/rmCvaAxIWT
📊 Answers and discussions for yesterday's quiz on sorting. Clearly what's been on everyone's minds since yesterday evening!
— Clément Canonne (@ccanonne_) October 2, 2020
To recap: you have an array of n numbers (integers), and want to end up with a sorted array, and, frankly, don't we all.
1/19 https://t.co/RgXVRzW6PP
📊 It's Thursday, allegedly: time for our wækly quiz. So, completely unrelated to anything, this one's going to be about influence, majority, tribes, noise, and dictators.
— Clément Canonne (@ccanonne_) September 24, 2020
(I didn't get "chaos" in, but I'm keeping that option open for the future. #gaussianchaos )
1/11 pic.twitter.com/eeRtkIpNmr
📊 Answers and discussion for yesterday's quiz on voting rules (a.k.a. Boolean functions for social choice).↴
— Clément Canonne (@ccanonne_) September 26, 2020
Disclaimer: for a much better and comprehensive treatment, @BooleanAnalysis 's book is the place to look ( https://t.co/f9OGjFKAVu ).
1/ https://t.co/jy0JzLWwiq
📊 It's (weakly) Thursday: time for a weekly quiz. For this one let's be merry, and play games—repeatedly!
— Clément Canonne (@ccanonne_) September 10, 2020
But, what's a game? You have 2 players, Alice 👩🏻💻 and Bob 👨🏾💻, and a game master, say Guillaume🧔🏼. Guillaume draws (x,y), gives (separately!) x to Alice and y to Bob...
1/9 pic.twitter.com/NMYxoRelJ5
📊 Answers and discussion for yesterday's quiz on games. Technically, "repeated games and direct product (parallel repetition) theorems."
— Clément Canonne (@ccanonne_) September 11, 2020
Or, as one may put it: if I keep playing, how likely is it that I'll keep winning?🤷
1/15 https://t.co/TvjcHG52Gf
📊 It may not be Thursday everywhere yet, but let's have our weakly(weekly(quiz))!
— Clément Canonne (@ccanonne_) September 3, 2020
Today: no general theme. Just things that may be true, or false, and surprisingly so―or not. Beware of the traps.
1/7 pic.twitter.com/VL50ZjMgS8
📊Answers and discussion for yesterday's quiz on "Things I Probably Would Have Gotten Wrong (Did You?)"
— Clément Canonne (@ccanonne_) September 4, 2020
Ft. Complexity theory (Q1), Probability (Q2), Measure theory (Q4), Planar graphs and pandas 🐼 (Q5), and Linear algebra (Q3)... in that order.
1/13 https://t.co/AG9nyiCw5F
📊 It's Thursday for many, time for this week's quiz! As alluded earlier, we're going to flip coins. Like, a lot.
— Clément Canonne (@ccanonne_) August 27, 2020
Today: you have a biased coin which lands heads with some probability p∊(0,1), and you can toss it as many times as you want. You don't know p, though...
1/10 pic.twitter.com/YCYEzSC5zJ
📊 Answers and discussion for yesterday's quiz on coin flipping (a.k.a. the power of small change?)
— Clément Canonne (@ccanonne_) August 28, 2020
Reminder: given a fixed function f, we want a procedure which given independent coin flips from a coin unknown probability of heads p ("bias")...
1/14 https://t.co/GThwTq3VPB
📊 It's Thursday, time for a we•kly quiz! As promised last week, today will be about Gaussians, CLTs, Berry—Esseen, and a little bit of Invariance Principle.
— Clément Canonne (@ccanonne_) August 20, 2020
Let's start. You have n i.i.d. real-valued r.v.s X₁,...,Xₙ, with mean zero. You sum them, and hope for the best.
1/10 pic.twitter.com/vWuIrcxO62
📊 Answers and discussion for yesterday's quiz on CLTs, Gaussians, and a bit of Invariance Principle.
— Clément Canonne (@ccanonne_) August 21, 2020
Let's start: Q1 on the Central Limit Theorem was a trap 🧐!
1/16 https://t.co/AqzMX6YdgI
📊 It's Thursday [reference needed], time for a weᵄekly quiz! Given some recent events about randomized polynomial time (RP), it feels like a short discussion about 🎲 is topical.
— Clément Canonne (@ccanonne_) August 6, 2020
So, let's go: Las Vegas, Monte Carlo, and... Bellagio (?) algorithms!
1/8 pic.twitter.com/DYFqOeMG8q
📊Thread: answers and discussions for yesterday's quiz on randomized complexity classes (RP, ZPP, BPP).
— Clément Canonne (@ccanonne_) August 7, 2020
Of course, I am barely scratching the surface. I find randomness in computation fascinating, and hope you will too. https://t.co/DQNWorXxa0
1/15 pic.twitter.com/CIFcqaqaF8
📊 Today, (weakly|weekly) quiz will be about graphs. The ones with nodes and edges, not those plotting against you.
— Clément Canonne (@ccanonne_) July 30, 2020
Specifically, *planar* graphs. The nice ones.
1/7
📊 Answers and discussion for yesterday's quiz on planar graphs. Recall: a graph G=(V,E) on n=|V| vertices and m=|E| edges is planar if you can "embed it in the plane" (draw it without edge crossings). 🕸️
— Clément Canonne (@ccanonne_) July 31, 2020
Why should we care, you ask?
1/10 https://t.co/yGrMgZ9ndB
📊 It's Thursday: time for our wÆkly quiz! I'll build a little bit on last week's statistics/algorithms thread (see below for a recap), and ask you two 2️⃣ questions.
— Clément Canonne (@ccanonne_) July 23, 2020
General topic: testing distributions, "leaky" measurements, and adaptivity. 🔍
1/6 https://t.co/YhEpCn4yov pic.twitter.com/aj5mYWKqkp
📊 Answers and discussions for yesterday's we(a)ekly quiz on "testing whether data is uniformly distribution, given some leaky query access to the samples." #statistics #quiz
— Clément Canonne (@ccanonne_) July 24, 2020
To paraphrase Tolstoy when starting "War and Peace": I'll be brief. https://t.co/NMK2GJ2DqF
1/10
📊 Two days ago, I asked a question. Way more people answered than expected, and... well, this week's weₐekly #quiz will be slightly ≠: a long thread on uniformity testing, trickling down all day long.
— Clément Canonne (@ccanonne_) July 16, 2020
Be careful what you wish for :) #statistics
1/n https://t.co/3ECldvbekE
📊 A short discussion about last week's thread on uniformity testing: I wrote things down!
— Clément Canonne (@ccanonne_) July 20, 2020
📝 https://t.co/jLEIKSxMIi (LaTeX)
📄 https://t.co/Uqq0yjWrwp (PDF)
Comments welcome.
1/2 https://t.co/6jqSvwoabC pic.twitter.com/1baBnVWWVl
📊 It's Thursday (somewhere), time for a weₐekly quiz! Today: #machinelearning ! Ish. Let's say... computational learning. Some of it. In theory.
— Clément Canonne (@ccanonne_) July 9, 2020
OK. VC dimension. You got me. Anyways, #COLT2020 is starting tomorrow, so... what does it mean to "learn," exactly?
1/10
📊 Answers and comments about yesterday's online quiz on learning.
— Clément Canonne (@ccanonne_) July 10, 2020
Not a quiz on online learning. Though there was an (online learning) component on that online (learning quiz), which maybe led to some learning online, so... I am confused now. https://t.co/2VO9AqXudR
1/16 pic.twitter.com/rNmo5tmwWM
📊 Wæekly quiz: "The answer may surprise you (or not)."
— Clément Canonne (@ccanonne_) July 2, 2020
Four results I find surprising (among many). Three of the statements below are true, one is false. Choose... wisely.
1/11 pic.twitter.com/lAV5UMTwRh
⁉️ Answers and discussion for yesterday's quiz: and yes, you are a Ravenclaw. (BuzzFeed has nothing on me.) https://t.co/csDmh8T4bk
— Clément Canonne (@ccanonne_) July 4, 2020
First I'd like to apologize for the original erroneous phrasing of Q1. If your answer was wrong, it was my fault.
[As usual, refs at the end]
1/19 pic.twitter.com/aODklwZQKB
📊 Weᵃₑkly quiz: linear threshold functions (a.k.a. perceptrons, a.k.a. halfspaces), and what makes them so unique.
— Clément Canonne (@ccanonne_) June 25, 2020
In other words, "the Chow Parameters."
Let's start with Boolean functions: i.e., functions of the form f: {-1,1}ⁿ→{-1,1}. There are 2^2^n of those.
1/9 pic.twitter.com/jJVRaJnyQh
🧑🏫 Answers and discussions for yesterday's quiz on Boolean functions, halfspaces (LTFs), and Chow parameters.
— Clément Canonne (@ccanonne_) June 26, 2020
Our focus here will be functions of the form f: {-1,1}ⁿ→{-1,1} (i.e., bits=±1)
[References for all results at the end of the thread.]
1/18 https://t.co/RYVrBItOrn pic.twitter.com/NZjzVdFJn1
📊 Weakly weekly quiz: a short one—next week 's will be longer. "How do you prove you won't always fall short of your expectations?"
— Clément Canonne (@ccanonne_) June 18, 2020
(No, it not not about eating Cheerios on the sofa, or the last time I wore actual socks. It's about constant-probability statements.)
1/4 pic.twitter.com/fJN7fBYx8B
📊 Answers and discussions for yesterday's quiz: "minimal assumptions for X to be, with constant probability, no less than a constant fraction of 𝔼[X]?"
— Clément Canonne (@ccanonne_) June 19, 2020
E.g., if an algo find something w/ large value in expectation, can it do it w/ probability 1/10?
1/7 https://t.co/wH3dh5qtLd
📊 Weakly-weekly quiz: this week, "how hard is it to learn when you keep forgetting things?"
— Clément Canonne (@ccanonne_) June 11, 2020
(This quiz is about learning functions. The question applies to history as well...)
You observe a stream of labelled samples (xᵢ,yᵢ) where yᵢ=f(xᵢ), and want to learn f...
1/9 pic.twitter.com/OsryHLJyH4
📊 Answers and discussion for yesterday's quiz on sample/memory tradeoffs for learning: a thread. ↴
— Clément Canonne (@ccanonne_) June 12, 2020
Overall question: "how hard does it become to learn a (linear) function when the algorithm can't keep too much information in memory?"
1/11 https://t.co/VXHILDT8Ww
📊 For this edition of the weekly quiz, let's look at random sums of random things, and their tails.
— Clément Canonne (@ccanonne_) June 4, 2020
Specifically, we have some i.i.d. r.v.'s X₁,X₂,..., and some integer-valued (possibly infinite) r.v. T. We look at S = X₁+X₂+...+X_T.
1/7
📊 Answers and discussion about yesterday w(ee|ea)kly quiz on random sums: S = X₁+X₂+...+X_T, w/ Xₙ's independent and T itself an integer-valued random variable.
— Clément Canonne (@ccanonne_) June 5, 2020
Under mild assumptions on all those, what can we say about the tails of the sum S? https://t.co/uNnZUyfuTc
1/11 pic.twitter.com/ACoAo8m5pe
📊 Today's weₐekly quiz: a 3-series ∑ edition! Nothing too fancy, maybe a cute probability proof in disguise somewhere.
— Clément Canonne (@ccanonne_) May 28, 2020
Let's start: we all know—maybe love—the exponential function. For all k in ℝ, ∑ₙkⁿ/n! = eᵏ. Fair enough... butnwhat if we perturb things a bit?
1/5
🧑🏫 Answers and discussions for yesterday's quiz on "series that kind of look like the exponential one."
— Clément Canonne (@ccanonne_) May 29, 2020
If you couldn't see properly the questions (non-utf8er's gonna non-utf8), I had screenshots here: https://t.co/65TqGvrZh1
1/8 https://t.co/e7Y1ChYOAI
📊 Here we go again: we{e,a}kly quiz. Let's have a look at two of our basic* friends, the Poisson 🐟 and Binomial 🐪 distributions. And what happens when they meet.
— Clément Canonne (@ccanonne_) May 21, 2020
Just so we're all on the same page: X~Binom(n,p) if X=∑ₖ Xₖ (n terms)...
*"I'm not basic. THEY're basic."
1/6
Answers and discussions for yesterday's quiz on Poisson 🐟, Binomial 🐪, and I guess 🐘 distributions.
— Clément Canonne (@ccanonne_) May 22, 2020
Here's the plan: answers, discussion of what a "Poisson Binomial distribution" 🐡 is and what it's for, related references.
1/9 https://t.co/di7wk0I48I
📊 It's time for a (short) installment of our weakly quiz. Setup: you are a *deterministic* algorithm 🤖 (sorry). You're given i.i.d. draws from some discrete distribution p over [n]={1,2..,n}, *close-ish* to uniform. You want to output i.i.d. draws *closer* to uniform.
— Clément Canonne (@ccanonne_) May 14, 2020
1/4
📊 Answers for yesterday's quiz: "if you're given i.i.d. samples from something close* from uniform on n elements, can you deterministically combine them to get something more uniform**? ↴
— Clément Canonne (@ccanonne_) May 15, 2020
* within TV distance ε
** within TV distance ε'
1/9 https://t.co/LYNwhDFNzS
📊 Here is a *semi non-technical* weekly quiz: a two-parter, first with an opinion poll, then a one-question quizz.
— Clément Canonne (@ccanonne_) April 30, 2020
Q1: What would you like these quizzes (and/or this account) to focus on more in the future? 🙋
1/3
Answers and discussions for yesterday's poll+quiz: thread below. ↴
— Clément Canonne (@ccanonne_) May 1, 2020
First, the poll: random stuff, and probability distribution-related things win the day. I won't promise puns will disappear, though. As a TCS person, I have promise problems.
1/6 https://t.co/iAMBxcjHbo
📊It's Thursday, time for a we[ae]kly quiz! Let's talk about juntas. The non-military kind.
— Clément Canonne (@ccanonne_) April 23, 2020
(As usual, questions below, answers tomorrow)
What is a junta? Basically, a very misleading function. For simplicity, think of f:{0,1}ⁿ→{0,1} (the def generalizes to f:Σⁿ→ℝ)..
1/7
⌛Time for the answers to yesterday's quiz on junta functions*! See thread below. ↴
— Clément Canonne (@ccanonne_) April 24, 2020
* "Technically n variables, morally k ≪ n"
1/12 https://t.co/x4QISb3Kyn
Weakly weekly quiz, new installment! I'm assuming everyone is very busy with either the #FOCS2020 deadline, the #ICML2020 reviews, or the current global health crisis and juggling with 5 toddlers & 7 Zoom online classes, so I'll keep it short.
— Clément Canonne (@ccanonne_) April 9, 2020
Adaptivity 🗘 and testing 🔎.
1/7
📚 Here are (a day late) the answers to this week's quiz on adaptivity 🗘 in property testing 🥚. A thread ↴
— Clément Canonne (@ccanonne_) April 11, 2020
1/10 https://t.co/1pcUXJ05Dt
🗒️ Today's quiz will be short, and focus on a very useful primitive called "hypothesis selection."
— Clément Canonne (@ccanonne_) March 26, 2020
Say you've got, as usual, data points coming from some unknown probability distribution p over some domain 𝓧. And you have a list of possible 'models' q₁, q₂,..., qₙ.
1/6
Answers and discussions for yesterday's quiz on hypothesis selection: a thread.
— Clément Canonne (@ccanonne_) March 27, 2020
The problem: you have data from some unknown probability distribution p, a list of n hypotheses q₁,..., qₙ. Assuming one of the qₜ's is good, find one 'not too bad.'
1/12 https://t.co/09lOKAy0Cl
📊 The weakly weekly quiz is back: in today's edition, "learning and testing, how are they related?" Specifically, we're going to look at functions f: {0,1}ⁿ→{0,1} and probability distributions p on a domaine of size [k].
— Clément Canonne (@ccanonne_) March 19, 2020
Hope you find that enjoyable. 1/11
Answers and discussions for yesterday's quiz on learning v. testing Boolean functions and probability distributions: a thread. 🧵 https://t.co/dG0N5anxMW
— Clément Canonne (@ccanonne_) March 20, 2020
1/16
Quizz of the week: I'm slightly jetlagged, so it'll be a bit short. Let's about 📉*monotone* 📈 probability distributions (univariate, discrete).
— Clément Canonne (@ccanonne_) March 5, 2020
That is, you have a distribution p over [k] = {1,2,...,k}, and you know its probability mass function is (wlog) non-increasing.
1/6
Answers and discussion for yesterday's polls on inference for (discrete) monotone distributions 📈📉 below. I hope you won't find it too... monotonous↴
— Clément Canonne (@ccanonne_) March 7, 2020
1/16 https://t.co/Tv1AdqRh7e
📊The past two weeks, we talked about learning (density estimation) of discrete distributions. Now, let's look at the flip side, and see a bit of what happens w/ *testing* (goodness-of-fit, hypothesis testing,...).
— Clément Canonne (@ccanonne_) February 27, 2020
All after, our distance measure will be total variation (TV)
1/8
Answers and discussion for yesterday's polls on testin 📊🐘 below. Some things, I'd say, are *far* from obvious.↴ https://t.co/gueiqlGBYA
— Clément Canonne (@ccanonne_) February 28, 2020
1/14
So last week was density estimation (distribution learning) of distributions 📊 over a domain of size k in total variation, Hellinger, and KL distances. Now you may wonder: "What about the rest?"
— Clément Canonne (@ccanonne_) February 20, 2020
Let's see some of the rest: ℓ₂, ℓ_∞, and Kolmogorov.
First: "Kolmogorov"?
1/9
Answers and discussion for yesterday's poll on "density estimation in other distances, such as Kolmogorov" below The answer MAY surprise you (with probability ≥ 0.428). ↴
— Clément Canonne (@ccanonne_) February 21, 2020
1/9 https://t.co/6jo6kAhKtT
📊 Learning discrete distributions over a finite domain, a short thread.↴
— Clément Canonne (@ccanonne_) February 15, 2020
Given n i.i.d. samples from some unknown p over a domain of size k and parameters ε,δ, you want to output some hypothesis q s.t.
d(p,q) < ε
with probability at least 1-δ. How large must n be?
1/8
📊 So, the results... Learning discrete distributions over a finite domain of size k to distance ε, with probability 1-δ: how hard can it be?
— Clément Canonne (@ccanonne_) February 16, 2020
1/9 https://t.co/AANZoxkm95
Test your intuition (or, in my case, lack thereof): hypothesis testing in high dimensions. You are given n i.i.d. samples from an unknown multivariate Gaussian p = N(μ,Σ) in ℝ^d. You want to know if p is *the* standard Gaussian N(0,I). 1/8
— Clément Canonne (@ccanonne_) October 27, 2019
So, the answers:
— Clément Canonne (@ccanonne_) October 28, 2019
- Q1 and Q2 both have the same one, √d/ε².
The fact that it's the same comes from the discussion on equivalent between TV to N(0,I) and ℓ₂ norm of the mean.
Learning the mean to ε in ℓ₂ would be d/ε². But estimating ||μ||₂ is quadratically cheaper! 1/8