Clément Canonne
@ccanonne.github.io
Senior Lecturer #USydCompSci at the University of Sydney. Postdocs IBM Research and Stanford; PhD at Columbia. Converts ☕ into puns: sometimes theorems. He/him.
Pinned
Clément Canonne
@ccanonne.github.io
· Nov 15
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]
📖 ccanonne.github.io/survey-topic... [Latest draft+exercise solns, free]
📗 nowpublishers.com/article/Deta... [Official pub]
📝 github.com/ccanonne/sur... [LaTeX source]
I was born too late
February 10, 2026 at 6:09 AM
I was born too late
Addendum: Also, as pointed out by @gautamkamath.com, this thread does not make explicit the fact that O(2^(n/2)) queries are sufficient for classical randomized algos. (See arxiv.org/abs/2102.06963 for a discussion of why.)
Classical algorithms for Forrelation
We study the forrelation problem: given a pair of $n$-bit Boolean functions $f$ and $g$, estimate the correlation between $f$ and the Fourier transform of $g$. This problem is known to provide the lar...
arxiv.org
February 10, 2026 at 5:54 AM
Addendum: Also, as pointed out by @gautamkamath.com, this thread does not make explicit the fact that O(2^(n/2)) queries are sufficient for classical randomized algos. (See arxiv.org/abs/2102.06963 for a discussion of why.)
Last thing: for those interested, a bent Boolean function f is a function whose 2^n Fourier coeffs all have the same magnitude, 2^(-n/2). Great! choose f from a suitable family and set g=±2^(n/2) ^f to get a Forrelation yes- or no-instance.
But now, WHICH FAMILY of bent functions to choose for f?
But now, WHICH FAMILY of bent functions to choose for f?
a close up of a bald man 's face with his eyes closed and a serious look on his face .
Alt: Vin Diesel with his eyes closed and a serious look on his face .
media.tenor.com
February 10, 2026 at 4:18 AM
Last thing: for those interested, a bent Boolean function f is a function whose 2^n Fourier coeffs all have the same magnitude, 2^(-n/2). Great! choose f from a suitable family and set g=±2^(n/2) ^f to get a Forrelation yes- or no-instance.
But now, WHICH FAMILY of bent functions to choose for f?
But now, WHICH FAMILY of bent functions to choose for f?
Which brings us to our preprint, where we* show that even in this extremal regime, 2^(n/2) classical queries** remain necessary.
Key idea: a construction still based on bent functions, but a different type of bent functions we* found.
📝 Have a read! arxiv.org/abs/2602.07503
* Kenny
** (almost)
Key idea: a construction still based on bent functions, but a different type of bent functions we* found.
📝 Have a read! arxiv.org/abs/2602.07503
* Kenny
** (almost)
The Quantumly Fast and the Classically Forrious
We study the extremal Forrelation problem, where, provided with oracle access to Boolean functions $f$ and $g$ promised to satisfy either $\textrm{forr}(f,g)=1$ or $\textrm{forr}(f,g)=-1$, one must de...
arxiv.org
February 10, 2026 at 4:06 AM
Which brings us to our preprint, where we* show that even in this extremal regime, 2^(n/2) classical queries** remain necessary.
Key idea: a construction still based on bent functions, but a different type of bent functions we* found.
📝 Have a read! arxiv.org/abs/2602.07503
* Kenny
** (almost)
Key idea: a construction still based on bent functions, but a different type of bent functions we* found.
📝 Have a read! arxiv.org/abs/2602.07503
* Kenny
** (almost)
(screenshot from their paper, arxiv.org/abs/2508.02514)
Now, the eagle-eyed BlueSkyer may notice their lower bound in the extremal regime is 2^(n/4), not 2^(n/2). Bummer! Indeed, their own lower bound construction could only get you so far.. Not a problem with the analysis, the construction itself.
Now, the eagle-eyed BlueSkyer may notice their lower bound in the extremal regime is 2^(n/4), not 2^(n/2). Bummer! Indeed, their own lower bound construction could only get you so far.. Not a problem with the analysis, the construction itself.
Forrelation is Extremally Hard
The Forrelation problem is a central problem that demonstrates an exponential separation between quantum and classical capabilities. In this problem, given query access to $n$-bit Boolean functions $f...
arxiv.org
February 10, 2026 at 4:06 AM
(screenshot from their paper, arxiv.org/abs/2508.02514)
Now, the eagle-eyed BlueSkyer may notice their lower bound in the extremal regime is 2^(n/4), not 2^(n/2). Bummer! Indeed, their own lower bound construction could only get you so far.. Not a problem with the analysis, the construction itself.
Now, the eagle-eyed BlueSkyer may notice their lower bound in the extremal regime is 2^(n/4), not 2^(n/2). Bummer! Indeed, their own lower bound construction could only get you so far.. Not a problem with the analysis, the construction itself.
And yes, the lower bound techniques used in pretty much all previous work failed in the "extremal" regime, ε→1. The functions used failed to be Boolean!
Until recently, when Girish and Servdio showed, using a completely different construction based on "bent functions", that yep—it remains hard!
Until recently, when Girish and Servdio showed, using a completely different construction based on "bent functions", that yep—it remains hard!
February 10, 2026 at 4:06 AM
And yes, the lower bound techniques used in pretty much all previous work failed in the "extremal" regime, ε→1. The functions used failed to be Boolean!
Until recently, when Girish and Servdio showed, using a completely different construction based on "bent functions", that yep—it remains hard!
Until recently, when Girish and Servdio showed, using a completely different construction based on "bent functions", that yep—it remains hard!
But this has to be hard classically, right? The Fourier transform of g isn't sthg very easy to get a grip on in a few queries... and indeed, it's hard! For ε up to 2/π≈0.64, Aaronson and Ambainis showed that any classical algo needed ~2^(n/2) queries.
2^(n/2) is a LOT more than 1. But.. ε < 2/π??
2^(n/2) is a LOT more than 1. But.. ε < 2/π??
February 10, 2026 at 4:06 AM
But this has to be hard classically, right? The Fourier transform of g isn't sthg very easy to get a grip on in a few queries... and indeed, it's hard! For ε up to 2/π≈0.64, Aaronson and Ambainis showed that any classical algo needed ~2^(n/2) queries.
2^(n/2) is a LOT more than 1. But.. ε < 2/π??
2^(n/2) is a LOT more than 1. But.. ε < 2/π??
In the Forrelation task, an algo is given some ε in (0,1] and query access to f,g: {0,1}^n→{0,1}, with the promise that f *and the Fourier transform of g* have correlation at least ε, or at most -ε. Task: figure out which!
That's a task easy by design for quantum algos, "because Hadamard": 1 query!
That's a task easy by design for quantum algos, "because Hadamard": 1 query!
hulk says " i was made for this " in front of a gray background
Alt: The Hulk says " i was made for this " in front of a gray background
media.tenor.com
February 10, 2026 at 4:06 AM
In the Forrelation task, an algo is given some ε in (0,1] and query access to f,g: {0,1}^n→{0,1}, with the promise that f *and the Fourier transform of g* have correlation at least ε, or at most -ε. Task: figure out which!
That's a task easy by design for quantum algos, "because Hadamard": 1 query!
That's a task easy by design for quantum algos, "because Hadamard": 1 query!
The paper is up! A project impressively led by Kenny Chen, co-advised with Julian Mestre, on Forrelation, a slightly-artificial up task introduced by Aaronson to show an exponential separation between classical and quantum computers.* Small 🧵 below!
📝 arxiv.org/abs/2602.07503
*(in the query model)
📝 arxiv.org/abs/2602.07503
*(in the query model)
February 10, 2026 at 4:06 AM
The paper is up! A project impressively led by Kenny Chen, co-advised with Julian Mestre, on Forrelation, a slightly-artificial up task introduced by Aaronson to show an exponential separation between classical and quantum computers.* Small 🧵 below!
📝 arxiv.org/abs/2602.07503
*(in the query model)
📝 arxiv.org/abs/2602.07503
*(in the query model)
Reposted by Clément Canonne
🎉 Yuan Sha and Joachim Gudmundsson's paper "Linear time single-source shortest path algorithms in Euclidean graph classes" has been accepted at #SoCG2026!
🔗 More about SoCG'26: computational-geometry.org/cg-week/socg/
👤 @jgudmundsson.bsky.social
#computationalgeometry #theory #algorithms
🔗 More about SoCG'26: computational-geometry.org/cg-week/socg/
👤 @jgudmundsson.bsky.social
#computationalgeometry #theory #algorithms
Computational Geometry
computational-geometry.org
February 10, 2026 at 12:20 AM
🎉 Yuan Sha and Joachim Gudmundsson's paper "Linear time single-source shortest path algorithms in Euclidean graph classes" has been accepted at #SoCG2026!
🔗 More about SoCG'26: computational-geometry.org/cg-week/socg/
👤 @jgudmundsson.bsky.social
#computationalgeometry #theory #algorithms
🔗 More about SoCG'26: computational-geometry.org/cg-week/socg/
👤 @jgudmundsson.bsky.social
#computationalgeometry #theory #algorithms
Those are some drawing skills you've got
February 9, 2026 at 9:13 PM
Those are some drawing skills you've got
Petition to rename the magic states |☕ ⟩, to please the Melbourne people.
It's coffee, not T!
It's coffee, not T!
February 9, 2026 at 8:20 PM
Petition to rename the magic states |☕ ⟩, to please the Melbourne people.
It's coffee, not T!
It's coffee, not T!
Reminder: please consider filling this form if you can, it takes 2mn (or less)! forms.gle/xrvc2mLRbMqK...
Theoretical CS community! I have a small favor to ask. If you ever used, read, watched some of the (excellent IMO) exposition content by Ryan O'Donnell, would you mind filling this very short survey, and maybe say how useful to you it was?
📝 forms.gle/xrvc2mLRbMqK...
Please spread this! #TCSSky
📝 forms.gle/xrvc2mLRbMqK...
Please spread this! #TCSSky
February 9, 2026 at 7:34 PM
Reminder: please consider filling this form if you can, it takes 2mn (or less)! forms.gle/xrvc2mLRbMqK...
Realized how to frame my question as an optimization problem to apply gradient descent.
It's all downhill from here.
It's all downhill from here.
February 9, 2026 at 4:44 AM
Realized how to frame my question as an optimization problem to apply gradient descent.
It's all downhill from here.
It's all downhill from here.
Reposted by Clément Canonne
Super cool expository paper on block designs and local differential privacy, showing a similar result to mine from last year but for a broader class of protocols ("pure" LDP functions and (r,λ)-designs)
arxiv.org/abs/2602.02744
arxiv.org/abs/2602.02744
An introduction to local differential privacy protocols using block designs
The design of protocols for local differential privacy (or LDP) has been a topic of considerable research interest in recent years. LDP protocols utilise the randomised encoding of outcomes of an expe...
arxiv.org
February 9, 2026 at 12:36 AM
Super cool expository paper on block designs and local differential privacy, showing a similar result to mine from last year but for a broader class of protocols ("pure" LDP functions and (r,λ)-designs)
arxiv.org/abs/2602.02744
arxiv.org/abs/2602.02744
Reposted by Clément Canonne
Theoretical CS community! I have a small favor to ask. If you ever used, read, watched some of the (excellent IMO) exposition content by Ryan O'Donnell, would you mind filling this very short survey, and maybe say how useful to you it was?
📝 forms.gle/xrvc2mLRbMqK...
Please spread this! #TCSSky
📝 forms.gle/xrvc2mLRbMqK...
Please spread this! #TCSSky
February 8, 2026 at 5:29 AM
Theoretical CS community! I have a small favor to ask. If you ever used, read, watched some of the (excellent IMO) exposition content by Ryan O'Donnell, would you mind filling this very short survey, and maybe say how useful to you it was?
📝 forms.gle/xrvc2mLRbMqK...
Please spread this! #TCSSky
📝 forms.gle/xrvc2mLRbMqK...
Please spread this! #TCSSky
Well, that'd be everyone.
February 8, 2026 at 10:18 AM
Well, that'd be everyone.
Reposted by Clément Canonne
Did you learn differential privacy (in part or in whole) from my course? Either the videos, lecture notes, or some combination? Please send me a DM or an email, I'm trying to gather some info.
(In case you missed it, here's the course: www.gautamkamath.com/CS860-fa2020..., ft full notes & videos)
(In case you missed it, here's the course: www.gautamkamath.com/CS860-fa2020..., ft full notes & videos)
CS 860 - Algorithms for Private Data Analysis- Fall 2020
www.gautamkamath.com
February 5, 2026 at 3:23 PM
Did you learn differential privacy (in part or in whole) from my course? Either the videos, lecture notes, or some combination? Please send me a DM or an email, I'm trying to gather some info.
(In case you missed it, here's the course: www.gautamkamath.com/CS860-fa2020..., ft full notes & videos)
(In case you missed it, here's the course: www.gautamkamath.com/CS860-fa2020..., ft full notes & videos)
(In case you're wondering why: this is to get some statistics and testimonies, related to this: sigact.org/prizes/trevi...)
February 8, 2026 at 5:31 AM
(In case you're wondering why: this is to get some statistics and testimonies, related to this: sigact.org/prizes/trevi...)
Theoretical CS community! I have a small favor to ask. If you ever used, read, watched some of the (excellent IMO) exposition content by Ryan O'Donnell, would you mind filling this very short survey, and maybe say how useful to you it was?
📝 forms.gle/xrvc2mLRbMqK...
Please spread this! #TCSSky
📝 forms.gle/xrvc2mLRbMqK...
Please spread this! #TCSSky
February 8, 2026 at 5:29 AM
Theoretical CS community! I have a small favor to ask. If you ever used, read, watched some of the (excellent IMO) exposition content by Ryan O'Donnell, would you mind filling this very short survey, and maybe say how useful to you it was?
📝 forms.gle/xrvc2mLRbMqK...
Please spread this! #TCSSky
📝 forms.gle/xrvc2mLRbMqK...
Please spread this! #TCSSky
(Forrelation=correlation+Fourier transform)
This can be solved with 1 quantum query to the oracles for f,g, but classically exponentially many queries (in n) are known to be necessary for most values of ε... Only the extremal case (eps=1, "as (anti)correlated as possible" was not fully understood.
This can be solved with 1 quantum query to the oracles for f,g, but classically exponentially many queries (in n) are known to be necessary for most values of ε... Only the extremal case (eps=1, "as (anti)correlated as possible" was not fully understood.
February 7, 2026 at 9:16 PM
(Forrelation=correlation+Fourier transform)
This can be solved with 1 quantum query to the oracles for f,g, but classically exponentially many queries (in n) are known to be necessary for most values of ε... Only the extremal case (eps=1, "as (anti)correlated as possible" was not fully understood.
This can be solved with 1 quantum query to the oracles for f,g, but classically exponentially many queries (in n) are known to be necessary for most values of ε... Only the extremal case (eps=1, "as (anti)correlated as possible" was not fully understood.
It's an (artificial) task that was introduced to show a quantum advantage over classical: given as input oracle access to two boolean functions f,g: {0,1}^n→{0,1} with the promise that the correlation <f,^g> is either <-ε or >ε (^g being the Fourier transform or g), one must decide which case holds.
February 7, 2026 at 9:13 PM
It's an (artificial) task that was introduced to show a quantum advantage over classical: given as input oracle access to two boolean functions f,g: {0,1}^n→{0,1} with the promise that the correlation <f,^g> is either <-ε or >ε (^g being the Fourier transform or g), one must decide which case holds.
Given that the object of study ("Forrelation") is already a pun/portmanteau, I think a little bit of levity in the title is absolutely fair game.
February 7, 2026 at 11:49 AM
Given that the object of study ("Forrelation") is already a pun/portmanteau, I think a little bit of levity in the title is absolutely fair game.
