Clément Canonne
@ccanonne.github.io
6.7K followers 570 following 2.3K posts
Senior Lecturer #USydCompSci at the University of Sydney. Postdocs IBM Research and Stanford; PhD at Columbia. Converts ☕ into puns: sometimes theorems. He/him.
Posts Media Videos Starter Packs
Pinned
ccanonne.github.io
Reminder/plug: my graduate-level monograph on "Topics and Techniques in Distribution Testing" (FnT Comm. and Inf Theory, 2022).

📖 ccanonne.github.io/survey-topic... [Latest draft+exercise solns, free]
📗 nowpublishers.com/article/Deta... [Official pub]
📝 github.com/ccanonne/sur... [LaTeX source]
Table of contents of the monograph
ccanonne.github.io
Or the other way around 👋
ccanonne.github.io
LET'S COLLABORATE LET'S COLLABORATE LET'S COLLABORATE 🐟
ccanonne.github.io
Today I saw a fish harassing a ray. The ray looked really annoyed. It just wanted to be left alone, the fish really wanted to interact.

I'm really upset about this: I don't know which one of the two I sympathize with more.
Reposted by Clément Canonne
focs2025.bsky.social
We're getting the summer ready for #FOCS2025.
A view of the Sydney Opera House from a ferry, with the city skyline on the left.
Reposted by Clément Canonne
sophie.huiberts.me
check out this quanta article about our recent work! Eleon will present it at @focs2025.bsky.social this december
quantamagazine.bsky.social
For nearly 80 years, an algorithm called the simplex method has been one of the most widely used tools for when a logistical decision needs to be made under complex constraints. A new update makes it faster than ever. www.quantamagazine.org/researchers-...
Researchers Discover the Optimal Way To Optimize | Quanta Magazine
The leading approach to the simplex method, a widely used technique for balancing complex logistical constraints, can’t get any better.
www.quantamagazine.org
ccanonne.github.io
This seems to be a typically Australian phenomenon, but...

It is a truth universally acknowledged, that a man in possession of a good fortune, must be in want of a leafblower. (Especially before 8am.)
ccanonne.github.io
I couldn't find a "lawyer" emoji, so there goes my "a notary transformation" follow-up. You've been spared (this time).
ccanonne.github.io
What do you call a quantum circuit that maps ∣0⟩ to ∣🦭⟩?

An otary transformation
ccanonne.github.io
"Graphic design is my passion" (creating a logo/poster)
A well-connected graph, whose nodes have emojis of various people, meant to represent the many faces of theoretical computer science
Reposted by Clément Canonne
dulwichquantum.bsky.social
Great list of quantum starter packs! 👇
christopher-k-long.bsky.social
With a long transfer from the Sahara to Fes, I finally finished going through the starter packs below. It was great to see everything you all have been working on! I like to spend some time reading through each profile, so I start to remember who's working on what. Please comment more starter packs!
Reposted by Clément Canonne
ccanonne.github.io
Attending #FOCS2025, or Theoretical CS (or adjacent) student in Australasia 🌏? On Dec 11-13, at #USyd, we will have a "Celebration of Theoretical CS" mentoring+research workshop. Amazing speakers, poster session, hike!

Free to attend (but registration is necessary): sites.google.com/view/celebra...
FOCS 2025 Satellite Event: Celebration of TCS
sites.google.com
ccanonne.github.io
Truly a fantastic line-up of speakers! Also: poster session (most likely involving gelato), reception, networking, Q&A: sites.google.com/view/celebra...

All that on the (beautiful) #USyd campus, in summery December, just before FOCS! #TCSSky
Confirmed Speakers
(Inspirational and Rising Stars)
Prof. Shafi Goldwasser (MIT)
Prof. Meena Mahajan (Institute of Mathematical Sciences, Chennai)
Ioana-Oriana Bercea (KTH)
Lorenzo Ciardo (Oxford University)
Jane Lange (MIT)
Yihui Quek (EPFL)
Santhoshini Velusamy (TTIC to University of Waterloo)
Hanzhi Wang (BARC to U Melbourne)
ccanonne.github.io
Attending #FOCS2025, or Theoretical CS (or adjacent) student in Australasia 🌏? On Dec 11-13, at #USyd, we will have a "Celebration of Theoretical CS" mentoring+research workshop. Amazing speakers, poster session, hike!

Free to attend (but registration is necessary): sites.google.com/view/celebra...
FOCS 2025 Satellite Event: Celebration of TCS
sites.google.com
ccanonne.github.io
Not that I can see (for instance, it's an equality, not an inequality). At least, the connection, if any, is not obvious to me.
Reposted by Clément Canonne
mcnees.bsky.social
“Why is the night sky dark, if we live in an infinite universe?”

Kepler, Halley, and Cheseaux all pondered this apparent paradox, but the question is commonly attributed to Heinrich Olbers, who was born #OTD in 1758. 🧪 🔭

Images: hyperphysics.phy-astr.gsu.edu/hbase/Astro/..., Wellcome Collection
A diagram shows arrows radiating from a central point, indicating directions, with lots of white disks (stars) surrounding the central point. An etching of Hans Olbers. He wears a heavy coat, vest, and high collared white shirt. His wispy hair is receding.
ccanonne.github.io
"With the whole GPU craze, now the most valuable rare metal is clearly potatium.
- You mean potassium?
- No, potatium. That's what they make chips from."
Reposted by Clément Canonne
ccanonne.github.io
With the same idea, one can show that if X, Y are independent random variables (both with finite variances) then

𝔼[(X-Y)²] = Var[X]+Var[Y]+(𝔼[X]-𝔼[Y])²

which in particular establishes the "standard useful fact" that, if X and Y are i.i.d., then 𝔼[(X-Y)²]=2Var[X].
ccanonne.github.io
With the same idea, one can show that if X, Y are independent random variables (both with finite variances) then

𝔼[(X-Y)²] = Var[X]+Var[Y]+(𝔼[X]-𝔼[Y])²

which in particular establishes the "standard useful fact" that, if X and Y are i.i.d., then 𝔼[(X-Y)²]=2Var[X].
ccanonne.github.io
Here's a classic (but fun to show) fact: if X is any random variable (with a finite variance) and λ is a real, then

𝔼[(X-λ)²] = Var[X]+(𝔼[X]-λ)²

(In particular, this shows that 𝔼[X] is the quantity minimizing 𝔼[(X-λ)²] over all λ, and that Var[X] is the resulting value.)
A short proof: here is the LaTeX code.

**Proof.** We have, for any $\color{blue}{\lambda} \in\mathbb{R}$,
\begin{align*}
\mathbb{E}[(X-\color{blue}{\lambda})^2]
&= \mathbb{E}[(X-\color{red}{\mathbb{E}[X]} + \color{red}{\mathbb{E}[X]} - \color{blue} {\lambda})^2] \\
&=\mathbb{E}[(X-\color{red}{\mathbb{E}[X]})^2 + 2(X-\color{red}{\mathbb{E}[X]})(\color{red}{\mathbb{E}[X]} - \color{blue} {\lambda}) + (\color{red}{\mathbb{E}[X]} - \color{blue} {\lambda})^2]\\
&=\underbrace{\mathbb{E}[(X-\color{red}{\mathbb{E}[X]})^2]}_{=\textrm{Var}[X]} + 2\underbrace{\mathbb{E}[X-\color{red}{\mathbb{E}[X]}]}_{=0}(\color{red}{\mathbb{E}[X]} - \color{blue} {\lambda})] + (\color{red}{\mathbb{E}[X]} - \color{blue} {\lambda})^2
\end{align*}
and that's all. (The first step is a trick known as *"hiding zero:"* writing $0=a-a$. 🤷)
ccanonne.github.io
(My original plan was 1000 🤷)