5 papers
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…
Clifford testing: algorithms and lower bounds
Marcel Hinsche, Zongbo Bao, Philippe van Dordrecht +3
We consider the problem of Clifford testing, which asks whether a black-box -qubit unitary is a Clifford unitary or at least -far from every Clifford unitary. We gi…
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 …
Grothendieck inequalities characterize converses to the polynomial method
Jop Briët, Francisco Escudero Gutiérrez, Sander Gribling
A surprising 'converse to the polynomial method' of Aaronson et al. (CCC'16) shows that any bounded quadratic polynomial can be computed exactly in expectation by a 1-query algorit…
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-…