7 papers
On Clifford hierarchy testing and near-extremizers of noncommutative uniformity norms
Zongbo, Bao, Jop Briët +3
We consider the problem of testing whether an unknown unitary is close to a specified level of the Clifford hierarchy. Bu, Gu, and Jaffe proposed a candidate tester for this task b…
An algorithmic Polynomial Freiman-Ruzsa theorem
Davi Castro-Silva, Jop Briët, Srinivasan Arunachalam +2
We provide algorithmic versions of the Polynomial Freiman-Ruzsa theorem of Gowers, Green, Manners, and Tao (Ann. of Math., 2025). In particular, we give a polynomial-time algorithm…
Symmetric quantum computation
Davi Castro-Silva, Tom Gur, Sergii Strelchuk
We introduce a systematic study of "symmetric quantum circuits", a new restricted model of quantum computation that preserves the symmetries of the problems it solves. This model i…
Algorithmic Polynomial Freiman-Ruzsa Theorems
Srinivasan Arunachalam, Davi Castro-Silva, Arkopal Dutt +1
We prove algorithmic versions of the polynomial Freiman-Ruzsa theorem of Gowers, Green, Manners, and Tao (Annals of Mathematics, 2025) in additive combinatorics. In particular, we…
A near-optimal Quadratic Goldreich-Levin algorithm
Jop Briët, Davi Castro-Silva
In this paper, we give a quadratic Goldreich-Levin algorithm that is close to optimal in the following ways. Given a bounded function on the Boolean hypercube …
On the threshold for Szemerédi's theorem with random differences
Jop Briët, Davi Castro-Silva
Using recent developments on the theory of locally decodable codes, we prove that the critical size for Szemerédi's theorem with random differences is bounded from above by $N^{1-…