A weₐᵉkly quiz on theoretical computer science (TCS), math, and random things.

📊 It's Thursday! Or Friday. Who knows anymore, and what is time? In any case, it's quizday! 🧩

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

— Clément Canonne (@ccanonne_) November 11, 2021

📊 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 ≥ ¾.

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

— Clément Canonne (@ccanonne_) November 14, 2021

📊 It's Thursday (for me), I have a coffee, time for a weekly quiz!

Today: Boolean circuits, functions, and functions which require large circuits.

1/ pic.twitter.com/J8Vpzg2XZm

— Clément Canonne (@ccanonne_) October 27, 2021

📊 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

1/

— Clément Canonne (@ccanonne_) October 30, 2021

📊 Since couplings have been on my mind lately, here is a very short, two-parter weₐᵉkly quiz.

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

— Clément Canonne (@ccanonne_) October 14, 2021

📊 (A bit overdue) answers and discussions for this week's quiz on Poisson v. Binomial, and stochastic dominance.

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

— Clément Canonne (@ccanonne_) October 17, 2021

📊 It's Friday here, still Thursday for many: time for our weekly quiz! Today: triangles ◁ △ ▷▽. In graphs! "Are there any?"

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

— Clément Canonne (@ccanonne_) October 7, 2021

📊 (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."

1/ https://t.co/pTcPTYBBIP

— Clément Canonne (@ccanonne_) October 9, 2021

📊 It's Thurfriday, time for our weekly quiz! Today, some probability puzzles: collisions!

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

— Clément Canonne (@ccanonne_) September 23, 2021

📊 Answers and discussion for this week's quiz on collisions: or, "how to best win cookies🍪 by playing weird random games."

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

— Clément Canonne (@ccanonne_) September 25, 2021

📊 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.

Because sometimes, you *really* want to solve those decision problems, don't you?

1/ pic.twitter.com/GsgBzQNl97

— Clément Canonne (@ccanonne_) September 9, 2021

📊 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

1/15

— Clément Canonne (@ccanonne_) September 12, 2021

📊 It's Thursday, time for a short weekly quiz! About a very basic problem: adding numbers.

Yes, counting. How hard can that be?

1/ pic.twitter.com/LNWB9jHLfF

— Clément Canonne (@ccanonne_) August 26, 2021

📊 Answers and discussion for this week's quiz on addition and circuit complexity. Addition: do something that counts!

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/

— Clément Canonne (@ccanonne_) August 28, 2021

📊 It's Thursday (it is!), time for a wₑeᵃkly quiz! A short one: let's not be greedy.

Yeah, let's not be greedy. Let's leave that to the algorithms! 🤖
1/ pic.twitter.com/n1OdVbWgQ2

— Clément Canonne (@ccanonne_) August 19, 2021

📊 Answers and discussions for this week's we(a)ekly quiz on greedy algorithms.

Remember: greedy's only a sin if you *forget* to try it!

1/ https://t.co/kK270ve3e6

— Clément Canonne (@ccanonne_) August 22, 2021

📊 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.

(Good ways, and bad ways.)

1/ pic.twitter.com/DnMXrD0cPy

— Clément Canonne (@ccanonne_) July 29, 2021

📊 Answers and discussions for this week's quiz on "distances between probability distributions." Or "how do I measure those things in a sensible way?"

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

— Clément Canonne (@ccanonne_) August 1, 2021

📊 It's Frursday*, time for a weekly quiz! Let's play a game, involving balls, and bins, and you throwing them.

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

— Clément Canonne (@ccanonne_) July 15, 2021

📊 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?

I have to admit, you've been quite good on this quiz. Maybe I should up my game.

1/ https://t.co/QKFkdvUa6Z

— Clément Canonne (@ccanonne_) July 18, 2021

📊 It's Friday/Thursday, depending on where you are: time for a (weakly) weekly quiz! This week: a (tiny glimpse) at lattice-based cryptography.

I'm not a specialist, so if I make any mistakes... we'll just call that "learning with errors"?

1/ pic.twitter.com/fZqVluiAcO

— Clément Canonne (@ccanonne_) July 8, 2021

📊 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.
1/ https://t.co/QsarURu21c

— Clément Canonne (@ccanonne_) July 12, 2021

📊 It's Thursday! Hope you're all staying safe. As promised, today's weekly quiz is #STOC21 (and, generally, broad-TCS) related.

[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

— Clément Canonne (@ccanonne_) June 24, 2021

📊 Answers and discussion for this week's quiz on (some aspects of) the history of Theoretical Computer Science, that is, TCS Factoids.

1/ https://t.co/M4l3roK0ND

— Clément Canonne (@ccanonne_) June 26, 2021

📊 It's Friday here, and Thursday there, and possibly in-between somewhere: time for a weekly quiz! Today, let's count stuff. Boolean functions.

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

— Clément Canonne (@ccanonne_) June 10, 2021

📊 Belated answers and discussion for last week's quiz on "how many of those Boolean functions are there?"

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

— Clément Canonne (@ccanonne_) June 15, 2021

📊 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?

[Spoiler: not a type of small rodents.]

1/ pic.twitter.com/ke6V4pIwld

— Clément Canonne (@ccanonne_) May 20, 2021

📊 Answers and discussion for this week's quiz on streaming and moment estimation.

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

— Clément Canonne (@ccanonne_) May 24, 2021

📊 It's Thursday [in many places], time for a weₐᵉkly quiz! As promised, this one's on #streaming . You know, Netflix, HBO?

Good. Not that.

1/ pic.twitter.com/bgQSktuXmr

— Clément Canonne (@ccanonne_) May 13, 2021

📊 Answers and discussion for this week's quiz on streaming and moment estimation.

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

— Clément Canonne (@ccanonne_) May 15, 2021

📊 It's Thursday-somewhere-Friday-here, time for a wᵉₐkly quiz. Today, 4 questions on communication!

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

— Clément Canonne (@ccanonne_) April 29, 2021

📊 Answers and discussion for this week's quiz on communication complexity with various types of shared randomness.

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

— Clément Canonne (@ccanonne_) May 1, 2021

📊 It's Thursday, time for a weekly quiz! We're on Twitter. Twitter is a social network. Social networks are basically graphs (with gifs).

Let's look at graphs (without gifs). But with gifs.

1/ pic.twitter.com/W44pjv7m7c

— Clément Canonne (@ccanonne_) April 22, 2021

📊 Answers and discussion for this week's quiz on graphs, cliques, and hardness of Max-Clique. "The answers may surprise you!"

(Yes, that was a clique-bait.)

1/ https://t.co/T6QOiUvur3

— Clément Canonne (@ccanonne_) April 24, 2021

📊 So, here is the answer, some discussion, and more questions about that
"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

— Clément Canonne (@ccanonne_) April 9, 2021

📊 Short thread: answers and proofs for the 3 extra questions on independent X,Y such that X+Y is Binomial.
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

— Clément Canonne (@ccanonne_) April 11, 2021

📊 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

Sorry: about Poissons, which are *random* fish.

1/6 pic.twitter.com/v5hnn8XeOv

— Clément Canonne (@ccanonne_) April 1, 2021

📊 After a long delay due to a long weekend: answers and discussion for last week's quiz on Poisson things.

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

— Clément Canonne (@ccanonne_) April 6, 2021

📊 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. 🪙

Formally, I give you a coin and a value p, and promise you it lands "heads" with proba either p or p+ε..

1/

— Clément Canonne (@ccanonne_) March 25, 2021

📊 Answers and discussions for this week's thread on distinguishing biased coins 🪙. Coin: it's like a die 🎲, but with two sides.

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/

— Clément Canonne (@ccanonne_) March 27, 2021

📊 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?

[In complexity terms: it's about L, NL, and SL. The labyrinth stuff is much catchier.]

1/ pic.twitter.com/jiDb9uD6Gy

— Clément Canonne (@ccanonne_) March 18, 2021

📊 Answers and discussions for this week's quiz: "how to get out of a maze when you have a really bad memory."

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

— Clément Canonne (@ccanonne_) March 20, 2021

📊 It's still Thursday! Time for a weekly quiz. On polling, deniability, and coffee.

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/

— Clément Canonne (@ccanonne_) March 12, 2021

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.

1/ https://t.co/b1Vbt1WlBI pic.twitter.com/SMM6Cy1Irs

— Clément Canonne (@ccanonne_) March 14, 2021

📊 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.

That is, it'll be about oracle machines and complexity classes.

1/ pic.twitter.com/rY3PsdNuVO

— Clément Canonne (@ccanonne_) March 4, 2021

📊 Answers and discussion for this week's quiz on complexity classes and "oracle machines"!

Before starting: if you're interested in computational complexity and are not already, follow @BooleanAnalysis , @rrwilliams , and @IgorCarboniOliv .

1/ https://t.co/XPl94x1w6S

— Clément Canonne (@ccanonne_) March 6, 2021

📊 It's Friday morning here (and Thursday in many other places, I'm told): time for a weekly quiz!

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

— Clément Canonne (@ccanonne_) February 18, 2021

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.*

The question is, what could that mean?
1/ https://t.co/nr7wLaXUvt

— Clément Canonne (@ccanonne_) February 21, 2021

📊 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.)

So you're given as input an array A of n numbers (weird gift, but why not).

1/

— Clément Canonne (@ccanonne_) February 11, 2021

📊 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?

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

— Clément Canonne (@ccanonne_) February 14, 2021

📊 It's Thursday (i.e., Friday 🇦🇺), it's been a while, and it's an installment of our (weakly) weekly quiz.

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

— Clément Canonne (@ccanonne_) February 4, 2021

Answers and discussion for this week's quiz on "do expectations and variances even exist? Does anything even exist? Wooow. 🤯"

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

— Clément Canonne (@ccanonne_) February 7, 2021

📊 Guess what: it's Thursday! Time for a (weakly) weekly quiz. This one may remind some of you of your randomized algorithms class🎲

"What to expect when we just do random stuff?"

1/ pic.twitter.com/p3ZWJOuLmL

— Clément Canonne (@ccanonne_) January 14, 2021

📊 Answers and discussions for this week's quiz on "doing random stuff and expecting things"

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

— Clément Canonne (@ccanonne_) January 17, 2021

📊 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.

Covering, packing, and ε-nets. Let's have a ball!

1/9 pic.twitter.com/cSahgJMsGN

— Clément Canonne (@ccanonne_) January 7, 2021

📊 Answers and discussion for this week's quiz: on covering, packing, and the importance of norms.

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

— Clément Canonne (@ccanonne_) January 9, 2021

📊 It's Thursday, time for a weₐᵉkly quiz! A two-parter, ft. Quantum Santa: merry Christmas, wherever you are!

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

— Clément Canonne (@ccanonne_) December 24, 2020

📊 Answers and discussions for this week's quiz on the communication complexity of |naughty∩nice|! 🤶

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

— Clément Canonne (@ccanonne_) December 26, 2020

📊 It is, if I am not mistaken, Thursday (in several parts of the world at least): time for a (weakly) weekly quiz!

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

— Clément Canonne (@ccanonne_) December 17, 2020

📊 Answers and discussion for yesterday's quiz on NP-Hardness of various things (or lack thereof).

Since I forgot to mention it yesterday, all graphs considered were undirected. Hopefully that didn't mislead anyone...

1/ https://t.co/J9n6tcw5DF

— Clément Canonne (@ccanonne_) December 18, 2020

📊 It's Thursday, time for our weekly (but weakly so) quiz! This week: integers, and remarkable sequences.

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

— Clément Canonne (@ccanonne_) December 3, 2020

📊 Answers and discussion for yesterday's quiz on sequences (and their names).

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

— Clément Canonne (@ccanonne_) December 4, 2020

📊 It's Thursday, it's Thanksgiving, and it's time for a (weakly) weekly quiz!

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

— Clément Canonne (@ccanonne_) November 26, 2020

📊 Answers and discussion for yesterday's Thanksquizzing 🦃: "theorem or random string of words?"

tl;dr: theorem, not theorem, theorem, theorem, not a theorem, theorem.

1/ https://t.co/mU516LZIt1

— Clément Canonne (@ccanonne_) November 27, 2020

📊 Thursday morning:* time for a weekly quiz! Let's talk about... POT!

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

— Clément Canonne (@ccanonne_) November 12, 2020

📊 Answers and discussions for Thursday's quiz! Let's look at the answers for those distinctions between (property) testing algorithms.

Quick recap: given a 'property' 𝒫 (subset of functions) and some access to some function f, accept if f∊𝒫.

1/12 https://t.co/8UmRqPGYAe

— Clément Canonne (@ccanonne_) November 14, 2020

📊 It's Thursday, and with it another weekly quiz! Since there is a lot going on these days, I'll keep it very short.

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

— Clément Canonne (@ccanonne_) November 5, 2020

📊 Answers and discussion for yesterday's short quiz on the Fibonacci sequence and a random variant 🎲.

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

— Clément Canonne (@ccanonne_) November 6, 2020

📊 Thursday! Time for an instance of our weekly (but weakly so) quiz.

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

— Clément Canonne (@ccanonne_) October 29, 2020

📊Answers and discussion for yesterday's quiz on prime numbers! The gist of the quiz was:
"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

— Clément Canonne (@ccanonne_) October 30, 2020

📊 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.

Some will be true, some false, and some will look like they could go both way.
1/8 pic.twitter.com/qMNcBIZ8h8

— Clément Canonne (@ccanonne_) October 22, 2020

📊 Answers and discussion for this week's quiz on inequalities between norms.

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

— Clément Canonne (@ccanonne_) October 24, 2020

📊 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🎈.

Specifically: when do they pop?
1/9 pic.twitter.com/Xd9TxZYUgW

— Clément Canonne (@ccanonne_) October 8, 2020

📊 Answers and discussion for yesterday's "pop quiz" on balloons🎈, and #learning .

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

— Clément Canonne (@ccanonne_) October 9, 2020

📊 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.

As people said to Louis XVI: "let's keep it short."

1/11 pic.twitter.com/rmCvaAxIWT

— Clément Canonne (@ccanonne_) October 1, 2020

📊 Answers and discussions for yesterday's quiz on sorting. Clearly what's been on everyone's minds since yesterday evening!

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

— Clément Canonne (@ccanonne_) October 2, 2020

📊 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.

(I didn't get "chaos" in, but I'm keeping that option open for the future. #gaussianchaos )

1/11 pic.twitter.com/eeRtkIpNmr

— Clément Canonne (@ccanonne_) September 24, 2020

📊 Answers and discussion for yesterday's quiz on voting rules (a.k.a. Boolean functions for social choice).↴

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

— Clément Canonne (@ccanonne_) September 26, 2020

📊 It's (weakly) Thursday: time for a weekly quiz. For this one let's be merry, and play games—repeatedly!

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

— Clément Canonne (@ccanonne_) September 10, 2020

📊 Answers and discussion for yesterday's quiz on games. Technically, "repeated games and direct product (parallel repetition) theorems."

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

— Clément Canonne (@ccanonne_) September 11, 2020

📊 It may not be Thursday everywhere yet, but let's have our weakly(weekly(quiz))!

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

— Clément Canonne (@ccanonne_) September 3, 2020

📊Answers and discussion for yesterday's quiz on "Things I Probably Would Have Gotten Wrong (Did You?)"

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

— Clément Canonne (@ccanonne_) September 4, 2020

📊 It's Thursday for many, time for this week's quiz! As alluded earlier, we're going to flip coins. Like, a lot.

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

— Clément Canonne (@ccanonne_) August 27, 2020

📊 Answers and discussion for yesterday's quiz on coin flipping (a.k.a. the power of small change?)

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

— Clément Canonne (@ccanonne_) August 28, 2020

📊 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.

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

— Clément Canonne (@ccanonne_) August 20, 2020

📊 Answers and discussion for yesterday's quiz on CLTs, Gaussians, and a bit of Invariance Principle.

Let's start: Q1 on the Central Limit Theorem was a trap 🧐!

1/16 https://t.co/AqzMX6YdgI

— Clément Canonne (@ccanonne_) August 21, 2020

📊 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.

So, let's go: Las Vegas, Monte Carlo, and... Bellagio (?) algorithms!

1/8 pic.twitter.com/DYFqOeMG8q

— Clément Canonne (@ccanonne_) August 6, 2020

📊Thread: answers and discussions for yesterday's quiz on randomized complexity classes (RP, ZPP, BPP).

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

— Clément Canonne (@ccanonne_) August 7, 2020

📊 Today, (weakly|weekly) quiz will be about graphs. The ones with nodes and edges, not those plotting against you.

Specifically, *planar* graphs. The nice ones.

1/7

— Clément Canonne (@ccanonne_) July 30, 2020

📊 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). 🕸️

Why should we care, you ask?

1/10 https://t.co/yGrMgZ9ndB

— Clément Canonne (@ccanonne_) July 31, 2020

📊 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.

General topic: testing distributions, "leaky" measurements, and adaptivity. 🔍

1/6 https://t.co/YhEpCn4yov pic.twitter.com/aj5mYWKqkp

— Clément Canonne (@ccanonne_) July 23, 2020

📊 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

To paraphrase Tolstoy when starting "War and Peace": I'll be brief. https://t.co/NMK2GJ2DqF

1/10

— Clément Canonne (@ccanonne_) July 24, 2020

📊 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.

Be careful what you wish for :) #statistics

1/n https://t.co/3ECldvbekE

— Clément Canonne (@ccanonne_) July 16, 2020

📊 A short discussion about last week's thread on uniformity testing: I wrote things down!

📝 https://t.co/jLEIKSxMIi (LaTeX)
📄 https://t.co/Uqq0yjWrwp (PDF)

Comments welcome.

1/2 https://t.co/6jqSvwoabC pic.twitter.com/1baBnVWWVl

— Clément Canonne (@ccanonne_) July 20, 2020

📊 It's Thursday (somewhere), time for a weₐekly quiz! Today: #machinelearning ! Ish. Let's say... computational learning. Some of it. In theory.

OK. VC dimension. You got me. Anyways, #COLT2020 is starting tomorrow, so... what does it mean to "learn," exactly?

1/10

— Clément Canonne (@ccanonne_) July 9, 2020

📊 Answers and comments about yesterday's online quiz on learning.

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

— Clément Canonne (@ccanonne_) July 10, 2020

📊 Wæekly quiz: "The answer may surprise you (or not)."

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

— Clément Canonne (@ccanonne_) July 2, 2020

⁉️ Answers and discussion for yesterday's quiz: and yes, you are a Ravenclaw. (BuzzFeed has nothing on me.) https://t.co/csDmh8T4bk
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

— Clément Canonne (@ccanonne_) July 4, 2020

📊 Weᵃₑkly quiz: linear threshold functions (a.k.a. perceptrons, a.k.a. halfspaces), and what makes them so unique.

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

— Clément Canonne (@ccanonne_) June 25, 2020

🧑‍🏫 Answers and discussions for yesterday's quiz on Boolean functions, halfspaces (LTFs), and Chow parameters.

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

— Clément Canonne (@ccanonne_) June 26, 2020

📊 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?"

(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

— Clément Canonne (@ccanonne_) June 18, 2020

📊 Answers and discussions for yesterday's quiz: "minimal assumptions for X to be, with constant probability, no less than a constant fraction of 𝔼[X]?"

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

— Clément Canonne (@ccanonne_) June 19, 2020

📊 Weakly-weekly quiz: this week, "how hard is it to learn when you keep forgetting things?"
(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

— Clément Canonne (@ccanonne_) June 11, 2020

📊 Answers and discussion for yesterday's quiz on sample/memory tradeoffs for learning: a thread. ↴

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

— Clément Canonne (@ccanonne_) June 12, 2020

📊 For this edition of the weekly quiz, let's look at random sums of random things, and their tails.

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

— Clément Canonne (@ccanonne_) June 4, 2020

📊 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.

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

— Clément Canonne (@ccanonne_) June 5, 2020

📊 Today's weₐekly quiz: a 3-series ∑ edition! Nothing too fancy, maybe a cute probability proof in disguise somewhere.

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

— Clément Canonne (@ccanonne_) May 28, 2020

🧑‍🏫 Answers and discussions for yesterday's quiz on "series that kind of look like the exponential one."

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

— Clément Canonne (@ccanonne_) May 29, 2020

📊 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.

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

— Clément Canonne (@ccanonne_) May 21, 2020

Answers and discussions for yesterday's quiz on Poisson 🐟, Binomial 🐪, and I guess 🐘 distributions.

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

— Clément Canonne (@ccanonne_) May 22, 2020

📊 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.

1/4

— Clément Canonne (@ccanonne_) May 14, 2020

📊 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**? ↴

* within TV distance ε
** within TV distance ε'

1/9 https://t.co/LYNwhDFNzS

— Clément Canonne (@ccanonne_) May 15, 2020

📊 Here is a *semi non-technical* weekly quiz: a two-parter, first with an opinion poll, then a one-question quizz.

Q1: What would you like these quizzes (and/or this account) to focus on more in the future? 🙋

1/3

— Clément Canonne (@ccanonne_) April 30, 2020

Answers and discussions for yesterday's poll+quiz: thread below. ↴

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

— Clément Canonne (@ccanonne_) May 1, 2020

📊It's Thursday, time for a we[ae]kly quiz! Let's talk about juntas. The non-military kind.
(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

— Clément Canonne (@ccanonne_) April 23, 2020

⌛Time for the answers to yesterday's quiz on junta functions*! See thread below. ↴

* "Technically n variables, morally k ≪ n"

1/12 https://t.co/x4QISb3Kyn

— Clément Canonne (@ccanonne_) April 24, 2020

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.

Adaptivity 🗘 and testing 🔎.

1/7

— Clément Canonne (@ccanonne_) April 9, 2020

📚 Here are (a day late) the answers to this week's quiz on adaptivity 🗘 in property testing 🥚. A thread ↴

1/10 https://t.co/1pcUXJ05Dt

— Clément Canonne (@ccanonne_) April 11, 2020

🗒️ Today's quiz will be short, and focus on a very useful primitive called "hypothesis selection."

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

— Clément Canonne (@ccanonne_) March 26, 2020

Answers and discussions for yesterday's quiz on hypothesis selection: a thread.

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

— Clément Canonne (@ccanonne_) March 27, 2020

📊 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].

Hope you find that enjoyable. 1/11

— Clément Canonne (@ccanonne_) March 19, 2020

Answers and discussions for yesterday's quiz on learning v. testing Boolean functions and probability distributions: a thread. 🧵 https://t.co/dG0N5anxMW

1/16

— Clément Canonne (@ccanonne_) March 20, 2020

Quizz of the week: I'm slightly jetlagged, so it'll be a bit short. Let's about 📉*monotone* 📈 probability distributions (univariate, discrete).
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

— Clément Canonne (@ccanonne_) March 5, 2020

Answers and discussion for yesterday's polls on inference for (discrete) monotone distributions 📈📉 below. I hope you won't find it too... monotonous↴
1/16 https://t.co/Tv1AdqRh7e

— Clément Canonne (@ccanonne_) March 7, 2020

📊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,...).
All after, our distance measure will be total variation (TV)
1/8

— Clément Canonne (@ccanonne_) February 27, 2020

Answers and discussion for yesterday's polls on testin 📊🐘 below. Some things, I'd say, are *far* from obvious.↴ https://t.co/gueiqlGBYA
1/14

— Clément Canonne (@ccanonne_) February 28, 2020

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?"
Let's see some of the rest: ℓ₂, ℓ_∞, and Kolmogorov.

First: "Kolmogorov"?
1/9

— Clément Canonne (@ccanonne_) February 20, 2020

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). ↴
1/9 https://t.co/6jo6kAhKtT

— Clément Canonne (@ccanonne_) February 21, 2020

📊 Learning discrete distributions over a finite domain, a short thread.↴
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

— Clément Canonne (@ccanonne_) February 15, 2020

📊 So, the results... Learning discrete distributions over a finite domain of size k to distance ε, with probability 1-δ: how hard can it be?
1/9 https://t.co/AANZoxkm95

— Clément Canonne (@ccanonne_) February 16, 2020

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:
- 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

— Clément Canonne (@ccanonne_) October 28, 2019