Clément Canonne

@ccanonne

Senior Lecturer #USydCompSci at the University of Sydney. Postdocs IBM Research and Stanford; PhD at Columbia. Converts ☕ into puns: sometimes theorems. He/him.

697 Siguiendo7279 Seguidores3439 Publicaciones

Bluesky

¿Es tu perfil?Reclámalo y ccanonne.dirty.social es tuyo.Reclamar perfil

Clément Canonne@ccanonne· 1d

Given the title of this review (opinion piece), feels pretty important to read the disclosure statement on that one.

Michael Noetel [...] is a director of Effective Altruism Australia.

Clément Canonne@ccanonne· 1d

This is beautiful! This should be better known! And the proof is... so simple, short, and neat. Read it—it's worth your time! 📝 www.stat.yale.edu/~yw562/teach... [Lecture notes by Yihong Wu on this result and proof (PDF)] /end

Chain rule for squared Hellinger distance (following TS Jayram)
Scribe: Max Lovig
Lecturer: Yihong Wu

Clément Canonne@ccanonne· 1d

So... does the inequality holds for arbitrary (not just product) distributions with square Hellinger? ALMOST! 🤯 This is surprisingly non-trivial, and this is surprisingly true, and this is due to T.S. Jayram (2009): it's true, if you put a weird constant in front of the RHS! 5/

Chain Rule-Type Inequality for Squared Hellinger, similar to the KL one but with a constant 3.46 in front of the RHS.

Clément Canonne@ccanonne· 1d

This is much better because of the squares there (this saves a quadratic factor in the dimension n, often crucial). But what if the distributions are *not* product distributions? Can we say anything? 🤔 We know (a suitable version) holds for *KL Divergence* (that's the chain rule!), after all! 3/

The chain rule for Kullback–Leibler divergence

Clément Canonne@ccanonne· 1d

"Well, of course not, duh." You could have all marginal distances equal to 0, yet LHS close to one (check it out!). It is true though for *product* distributions as a simple consequence of the triangle inequality (also holds for TV distance). But for products, we have the much stronger version: 2/

The subadditivity inequality, which holds for *squared* Hellinger distance when the distribution are product distributions.

Clément Canonne@ccanonne· 1d

As promised yesterday, a short thread on an inequality I believe deserves to be much better-known: a chain-rule-type for Hellinger distance! You have two probability distributions p,q over product space Ω₁×...×Ωₙ. Can you relate their distance H(p,q) to the distances between their marginals? 1/

The dream inequality (false): overall Hellinger is at most sum of Hellinger between marginals

Clément Canonne@ccanonne· 2d

It took us a while to work out the details, but our group finally formulated a detailed and consistent theory of quantum Pokémon! Also, please don't observe Psiduck, it stresses it out and it *will* collapse.

$A \psi, with a duck as a subscript$

Clément Canonne@ccanonne· 2d

So many good points in this post by @nsaphra.bsky.social: only quoting a couple, to encourage you to read the others. "My colleagues and students adopt the writing quirks they read throughout the day, and their own writing becomes more like an LLM’s." nsaphra.net/post/uncanny/

To find a nugget of meaning, the user must sift through mounds of slop—and some simply won’t bother. They’ll serve the slop unfiltered to another party, who performs this interpretive labor themselves, only to discover that the underlying meaning does not exist. When someone expects me to perform their share of this interpretive labor, I get angry. Grice’s rules are, in essence, rules of etiquette—their unwarranted violation is rude.

Clément Canonne@ccanonne· 3d

David Pollard has a new draft, "Probability tools, tricks, and miracles" (last updated June 2006). Lots of good things in there, from a quick skim! And, if nothing else, worth reading for the quality of the writing and the exposition choices and notes. www.stat.yale.edu/~pollard/Boo...

From the first chapter of the draft {"How I chose material for this book"):

I strongly believe in the value of seeing how an idea can develop from
an initial brilliant insight (a ‘miracle’) to a ‘trick’ (a method known to,
and often developed by, a few experts) to a ‘tool’ (a method that is well
understood and can be applied in settings, even those unsuspected by its
inventors). Indeed, one of the great pleasures in my research life has been
the progression from first wondering how anyone could have such a clever
idea to the final realization that everything depended on only a few stunning insights.

Clément Canonne@ccanonne· 5d

I'm (finally) reading the Australian Research Council (ARC)'s National Competitive Grants Program (NCGP) Policy Review, and... I'm no finance wizard, but if I had an investment scheme yielding 232% benefit, I'd consider investing slightly more in it? www.arc.gov.au/news-and-pub...

The NCGP represents 7% of the Australian Government’s total R&D spend and is an important driver of Australian university research. NCGP funding makes up more than a third of the Australian Government’s competitive research income received by universities1 and is a significant contributor to the calculation of Research Block Grant allocations. Since its inception, research funded through the NCGP has generated an estimated $3.32 for every dollar invested

Clément Canonne@ccanonne· 6d

I think of this, by Austin Kleon, often.

A text, mostly blacked out, with the remaining words stating "I mean yes, we're sinking. But the music is exceptional."

Clément Canonne@ccanonne· 6d

www.unsw.edu.au/science/abou... (Includes "climate modelling and prediction", by the way!)

The areas explicitly listed l:

Digital-led Discovery and Design of New Materials

Environmental Resilience: Prediction, Protection and Restoration

Discovery for Human Health

Clément Canonne@ccanonne· 6d

"If I have seen further than others, it's because I have been sitting on the chair of GIANTS"

Clément Canonne@ccanonne· 12d

Mathematicians! Book a function! Reserve a group! Looking for a nice... space?

A menu saying "Functions and group bookings
Looking for a space to connect with frienda and community?"

Clément Canonne@ccanonne· 16d

Saw the latest blog post by Bill Gasarch on @lance.fortnow.com's blog, and I need to get it out of my system: this is not "the obvious thing." This isn't insightful. This is, from a senior and respected member of our community, plainly disappointing. A ouija board w/ a varnish of misunderstood tech.

I wondered whether Paul Erdos would be happy with how it turned out. So I did the obvious thing: I asked Google AI

Would Erdos have liked the solution to the sum-product conjecture?

Here is what it said:

Clément Canonne@ccanonne· 22d

An aperiodic reminder that our community (theoretical computer science), while amazing, really sucks at naming things.

A slide introducing the complexity classes:

NP, coNP
Non-Deterministic Polynomial (and its dual) [no dice]
RP, coRP
Randomized Polynomial (and its dual)
BPP
Bounded-Error Probabilistic Polynomial
ZPP
Zero-Error Probabilistic Polynomial

Clément Canonne@ccanonne· 26d

Well. That is quite the headline from Le Monde Diplomatique.

A poster with the headline from the monthly edition of Le Monde Diplomatique: "Tout le monde déteste l'IA" (Everyone hates AI)

Clément Canonne@ccanonne· 27d

Workshop in the Club de la Chasse in Paris, a very old building moonlighting as a museum dedicated to... hunting? Seeing this place, it changes you.

My head, with antlers (from a trophy behind, on the wall)

Clément Canonne@ccanonne· Jul 12

Rummaging through my old lecture notes at my parents' house... found this exercise sheet. Good times.

In French, an exercise sheet. The first sentence: "One of the exercises below is truly infeasible. Find it, then solve the others."

Clément Canonne@ccanonne· Jul 7

"Wanting to learn is more interesting than believing you know"

A mural in Paris, with two people playing chess and the text "Vouloir apprendre eat plus imtéressant que penser savoir"

Clément Canonne@ccanonne· Jul 3

Welcome to France. This is an actual bus route

Two stops called Croissant and Chocolaterie

Clément Canonne@ccanonne· Jul 2

Pros: a dynamic and collegial department (School), expanding, with excellent researchers and wonderful colleagues, in an incredible city, in a beautiful country! Cons: some birds look funny

A sulphur-crested cockatoo, on the grass

Clément Canonne@ccanonne· Jul 1

Kenny's results improve on those recently obtained by Doosti, Sweke, and Wadhwa (arxiv.org/abs/2604.05962), who formalized this distributed quantum property testing setting (analogue of the classical setting Jayadev Acharya, Himanshu Tyagi and I introduced a few years ago) Truly impressed by Kenny!

Table summarizing the results, from Kenny's paper

Clément Canonne@ccanonne· Jun 27

Ah, yes, Burger King. "Pizza."

A Burger King ad (in France) saying "le foot, c'est forcément avec une bonne pizza" and showing people sharing small... Burgers

Clément Canonne@ccanonne· Jun 19

I will take two epsilons of caffeine, yes, thank you

A cup of coffee with a text, where the two "e" of "feels good" look like epsilons

Clément Canonne@ccanonne· Jun 8

These are meant to complement the second part of my course's lecture notes on randomized graph algorithms: ccanonne.github.io/files/compx2... (I'm not just subjecting students to my handwriting with nothing to save them)

p.68: beginning of the section on Minimum Spanning Tree in Expected Linear Time

Clément Canonne@ccanonne· Jun 8

The Karger–Klein–Tarjan algorithm (MST in expected linear time) is incredibly beautiful. A joy to teach and share (at least for me; at least one happy person in the classroom, I guess.) To compensate for how beautiful that algo is, I made handwritten slides: ccanonne.github.io/files/compx2...

Description of the key ideas behind the KKT algorithm: sparsify the graph G by finding a "good" forest F of the graph, which can be used to identify (and remove) a lot of "heavy" edges from G. Once G has been sparsified this way, finding an MST in what remains is much faster.

Clément Canonne@ccanonne· Jun 7

Exhibit A:

The ringtail possum, on the balcony railing

Clément Canonne@ccanonne· Jun 7

The Curious Incident of The Balcony Flower Being Eaten In the Night-Time

Clément Canonne@ccanonne· Jun 6

The long weekend starts well, with auspicious galahs!