pith. sign in

arxiv: 2604.04547 · v1 · submitted 2026-04-06 · 🧮 math.CO · cs.DS

An algorithmic Polynomial Freiman-Ruzsa theorem

Davi Castro-Silva , Jop Bri\"et , Srinivasan Arunachalam , Arkopal Dutt , Tom Gur This is my paper

Pith reviewed 2026-05-10 20:06 UTC · model grok-4.3

classification 🧮 math.CO cs.DS
keywords Polynomial Freiman-Ruzsa theoremalgorithmic additive combinatoricsquadratic Fourier analysissymplectic geometryGoldreich-Levin algorithmdoubling constantstructure versus randomness
0
0 comments X

The pith

A polynomial-time algorithm outputs a subspace V no larger than the input set A such that A is covered by at most 2K^C translates of V whenever A has doubling constant K.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper gives an efficient algorithmic version of the Polynomial Freiman-Ruzsa theorem in the vector space F_2^n. Given any set A whose sumset is at most K times larger than A itself, the procedure returns in polynomial time a subspace V whose size is at most |A| and whose translates cover A with only polynomially many copies in K. The same framework also yields polynomial-time algorithms for the polynomial Gowers inverse theorem, the classification of approximate Freiman homomorphisms, and quadratic structure-versus-randomness decompositions. The key technical step is a new optimal Quadratic Goldreich-Levin algorithm that rests on an explicit link between quadratic Fourier analysis and symplectic geometry.

Core claim

We provide algorithmic versions of the Polynomial Freiman-Ruzsa theorem of Gowers, Green, Manners, and Tao. In particular, we give a polynomial-time algorithm that, given a set A ⊆ F_2^n with doubling constant K, returns a subspace V ⊆ F_2^n of size |V| ≤ |A| such that A can be covered by 2K^C translates of V, for a universal constant C>1. We also provide efficient algorithms for several equivalent formulations of the Polynomial Freiman-Ruzsa theorem, such as the polynomial Gowers inverse theorem, the classification of approximate Freiman homomorphisms, and quadratic structure-vs-randomness decompositions. Our algorithmic framework is based on a new and optimal version of the Quadratic Goldr

What carries the argument

A new optimal Quadratic Goldreich-Levin algorithm derived from quantum learning theory that makes explicit the connection between quadratic Fourier analysis and symplectic geometry to locate quadratic phases efficiently.

If this is right

  • The polynomial Gowers inverse theorem admits an efficient algorithmic version.
  • Approximate Freiman homomorphisms can be classified in polynomial time.
  • Quadratic structure-versus-randomness decompositions can be computed efficiently.
  • The same framework yields polynomial-time procedures for several other equivalent formulations of the Polynomial Freiman-Ruzsa theorem.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The symplectic-geometry viewpoint may extend to algorithmic versions of higher-degree inverse theorems in additive combinatorics.
  • The quantum-learning-inspired technique could produce new classical algorithms for phase-finding tasks in property testing.
  • Implementations of the algorithm may improve detection of linear structure inside noisy high-dimensional data sets arising in coding theory.

Load-bearing premise

The input set A is promised to have doubling constant K, and the algorithm's correctness and runtime rely on this promise together with the existence of the non-algorithmic Polynomial Freiman-Ruzsa theorem.

What would settle it

An explicit set A in F_2^n with doubling constant K on which the algorithm either exceeds polynomial runtime or returns a subspace V with |V| ≤ |A| that requires more than 2K^C translates to cover A.

Figures

Figures reproduced from arXiv: 2604.04547 by Arkopal Dutt, Davi Castro-Silva, Jop Bri\"et, Srinivasan Arunachalam, Tom Gur.

Figure 1
Figure 1. Figure 1: Forbidden regions for y. Choose the angles between the straight lines and the horizontal axis to be such that the distance from the origin to the small circles equals r = p 1 − (γ − 1/2)2. If y lies outside of the annulus, then the first term of (29) is at least 1 4 (γ −1/2)2 |⟨f, ϕ⟩|8 . If y lies inside the annulus but outside of the small circles, then elementary trigonometry shows that the second term o… view at source ↗
read the original abstract

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 that, given a set $A \subseteq \mathbb{F}_2^n$ with doubling constant $K$, returns a subspace $V \subseteq \mathbb{F}_2^n$ of size $|V| \leq |A|$ such that $A$ can be covered by $2K^C$ translates of $V$, for a universal constant $C>1$. We also provide efficient algorithms for several "equivalent" formulations of the Polynomial Freiman-Ruzsa theorem, such as the polynomial Gowers inverse theorem, the classification of approximate Freiman homomorphisms, and quadratic structure-vs-randomness decompositions. Our algorithmic framework is based on a new and optimal version of the Quadratic Goldreich-Levin algorithm, which we obtain using ideas from quantum learning theory. This framework fundamentally relies on a connection between quadratic Fourier analysis and symplectic geometry, first speculated by Green and Tao (Proc. of Edinb. Math. Soc., 2008) and which we make explicit in this paper.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript develops algorithmic versions of the Polynomial Freiman-Ruzsa theorem of Gowers, Green, Manners, and Tao. The central result is a polynomial-time algorithm that, given A ⊆ F_2^n with doubling constant K, returns a subspace V ⊆ F_2^n satisfying |V| ≤ |A| such that A is covered by at most 2K^C translates of V for a universal constant C > 1. It also supplies efficient algorithms for several equivalent formulations, including the polynomial Gowers inverse theorem, the classification of approximate Freiman homomorphisms, and quadratic structure-vs-randomness decompositions. The framework rests on a new optimal Quadratic Goldreich-Levin procedure derived from quantum learning theory together with an explicit symplectic-geometry formulation of quadratic Fourier analysis.

Significance. If the claimed polynomial runtime and covering bound hold, the work is significant: it supplies the first efficient algorithmic realization of the Polynomial Freiman-Ruzsa theorem and thereby opens the door to algorithmic applications in additive combinatorics, property testing, and learning theory. The derivation of the Quadratic Goldreich-Levin algorithm from quantum ideas and the concrete symplectic-geometry connection are genuine technical contributions that strengthen the interface between analytic additive combinatorics and algorithmic techniques.

minor comments (3)
  1. The abstract states that the runtime is polynomial but does not indicate the degree of the polynomial or its dependence on n and K; a brief explicit statement in the introduction would improve readability.
  2. The paper invokes the non-algorithmic PFR theorem as a black box; a short paragraph clarifying precisely which statements are used and where the new analytic tools take over would help readers trace the reduction.
  3. Notation for the doubling constant K and the covering number 2K^C is introduced without an immediate reminder of the standard definition; adding a one-sentence recall in §1 would aid accessibility.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, the recognition of its significance, and the recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper derives an algorithmic Polynomial Freiman-Ruzsa theorem by reducing the problem to a new Quadratic Goldreich-Levin procedure obtained via quantum learning theory and an explicit symplectic-geometry formulation of quadratic Fourier analysis. The central algorithm invokes the non-algorithmic PFR theorem of Gowers-Green-Manners-Tao (distinct authors, 2025) only as an external existence result under the doubling promise; no step equates the output subspace or covering bound to a fitted parameter, self-defined quantity, or prior result by the present authors. All cited ingredients (Green-Tao speculation, quantum techniques) are independent of the target claim and do not reduce the derivation to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the existence of the non-algorithmic Polynomial Freiman-Ruzsa theorem (domain assumption) and on the correctness of the new quadratic algorithm derived from quantum ideas; no free parameters are fitted in the abstract and no new entities are postulated.

axioms (1)
  • domain assumption The Polynomial Freiman-Ruzsa theorem of Gowers, Green, Manners, and Tao holds.
    The algorithmic versions are stated as efficient realizations of this prior existence result.

pith-pipeline@v0.9.0 · 5526 in / 1218 out tokens · 76792 ms · 2026-05-10T20:06:02.846846+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

46 extracted references · 46 canonical work pages

  1. [1]

    Physical Review A 70(5) (Nov 2004)

    Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits.Phys. Rev. A, 70:052328, Nov 2004.doi:10.1103/PhysRevA.70.052328

    work page doi:10.1103/physreva.70.052328 2004

  2. [2]

    Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems

    Divesh Aggarwal, Yevgeniy Dodis, and Shachar Lovett. Non-malleable codes from additive com- binatorics. InProceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’14, page 774–783. Association for Computing Machinery, 2014.doi:10.1145/2591796. 2591804

    work page doi:10.1145/2591796 2014

  3. [3]

    Prentice Hall, Inc., Englewood Cliffs, NJ, 1991

    Michael Artin.Algebra. Prentice Hall, Inc., Englewood Cliffs, NJ, 1991

    work page 1991

  4. [4]

    Learning stabilizer structure of quantum states.To appear in STOC’26

    Srinivasan Arunachalam and Arkopal Dutt. Learning stabilizer structure of quantum states.To appear in STOC’26. arXiv:2510.05890, 2025

    work page arXiv 2025

  5. [5]

    Stochastic Matching via In-n-Out Local Computation Algorithms , booktitle =

    Srinivasan Arunachalam and Arkopal Dutt. Polynomial-time tolerant testing stabilizer states. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, page 1234–1241. Association for Computing Machinery, 2025.doi:10.1145/3717823.3718277

    work page doi:10.1145/3717823.3718277 2025

  6. [6]

    Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , author =

    Vahid R. Asadi, Alexander Golovnev, Tom Gur, and Igor Shinkar. Worst-case to average-case reductions via additive combinatorics. InProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, page 1566–1574. Association for Computing Machinery, 2022. doi:10.1145/3519935.3520041

    work page doi:10.1145/3519935.3520041 2022

  7. [7]

    Quantum worst-case to average-case reductions for all linear problems

    Vahid R Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, and Sathyawageeswar Subramanian. Quantum worst-case to average-case reductions for all linear problems. InProceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2535–2567. SIAM, 2024. doi:10.1137/1.9781611977912.90

    work page doi:10.1137/1.9781611977912.90 2024

  8. [8]

    Efficient algorithms and new characterizations for csp sparsification

    Zongbo Bao, Philippe van Dordrecht, and Jonas Helsen. Tolerant testing of stabilizer states with a polynomial gap via a generalized uncertainty relation. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, page 1254–1262. Association for Computing Ma- chinery, 2025.doi:10.1145/3717823.3718201

    work page doi:10.1145/3717823.3718201 2025

  9. [9]

    Tight pair query lower bounds for matching and earth mover’s distance

    Benjamin Bedert, Tamio-Vesa Nakajima, Karolina Okrasa, and Stanislav Zivn´ y. Strong sparsi- fication for 1-in-3-sat via Polynomial Freiman-Ruzsa. In2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pages 2470–2479, 2025.doi:10.1109/FOCS63196.2025. 00129

    work page doi:10.1109/focs63196.2025 2025

  10. [10]

    An additive combinatorics approach relating rank to communication complexity.Journal of the ACM (JACM), 61(4):1–18, 2014.doi:10.1145/ 2629598

    Eli Ben-Sasson, Shachar Lovett, and Noga Ron-Zewi. An additive combinatorics approach relating rank to communication complexity.Journal of the ACM (JACM), 61(4):1–18, 2014.doi:10.1145/ 2629598

    work page 2014

  11. [11]

    Fomin and Petr A

    Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, and Julia Wolf. Sampling-based proofs of almost- periodicity results and algorithmic applications. InInternational Colloquium on Automata, Lan- guages, and Programming, pages 955–966. Springer, 2014.doi:10.1007/978-3-662-43948-7\_79. 78 D. CASTRO-SILVA, J. BRI ¨ET, S. ARUNACHALAM, A. DUTT, AND T. GUR

    work page doi:10.1007/978-3-662-43948-7 2014

  12. [12]

    and Harrow, Aram W

    Abhishek Bhowmick, Zeev Dvir, and Shachar Lovett. New bounds for matching vector families. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’13, page 823–832. Association for Computing Machinery, 2013.doi:10.1145/2488608.2488713

    work page doi:10.1145/2488608.2488713 2013

  13. [13]

    Cambridge University Press, Cam- bridge, 2018

    Tullio Ceccherini-Silberstein, Fabio Scarabotti, and Filippo Tolli.Discrete harmonic analysis, volume 172 ofCambridge Studies in Advanced Mathematics. Cambridge University Press, Cam- bridge, 2018. Representations, number theory, expanders, and the Fourier transform.doi:10. 1017/9781316856383

    work page 2018

  14. [14]

    Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation

    Sitan Chen, Weiyuan Gong, Qi Ye, and Zhihan Zhang. Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation. InProceedings of the 57th Annual ACM Sym- posium on Theory of Computing, STOC ’25, page 429–438. Association for Computing Machinery, 2025.doi:10.1145/3717823.3718191

    work page doi:10.1145/3717823.3718191 2025

  15. [15]

    On the geometry of algebraic homogeneous spaces.Annals of Mathematics, 50(1):32–67, 1949.doi:10.2307/1969351

    Wei-Liang Chow. On the geometry of algebraic homogeneous spaces.Annals of Mathematics, 50(1):32–67, 1949.doi:10.2307/1969351

    work page doi:10.2307/1969351 1949

  16. [16]

    Clifford group, stabilizer states, and linear and quadratic operations over GF(2).Phys

    Jeroen Dehaene and Bart De Moor. Clifford group, stabilizer states, and linear and quadratic operations over GF(2).Phys. Rev. A, 68:042318, Oct 2003.doi:10.1103/PhysRevA.68.042318

    work page doi:10.1103/physreva.68.042318 2003

  17. [17]

    Large values of the Gowers-Host-Kra seminorms.Journal d’Analyse Math´ ematique, 117:133–186, 2012.doi:10.1007/s11854-011-0033-6

    Tanja Eisner and Terence Tao. Large values of the Gowers-Host-Kra seminorms.Journal d’Analyse Math´ ematique, 117:133–186, 2012.doi:10.1007/s11854-011-0033-6

    work page doi:10.1007/s11854-011-0033-6 2012

  18. [18]

    Latin American Mathematics Series

    Anahita Eslami Rad.Symplectic and contact geometry—a concise introduction. Latin American Mathematics Series. Springer, 2024.doi:10.1007/978-3-031-56225-9

    work page doi:10.1007/978-3-031-56225-9 2024

  19. [19]

    On sums of generating sets inZ n 2 .Combinatorics, probability and computing, 21(6):916–941, Nov 2012.doi:10.1017/S0963548312000351

    Chaim Even-Zohar. On sums of generating sets inZ n 2 .Combinatorics, probability and computing, 21(6):916–941, Nov 2012.doi:10.1017/S0963548312000351

    work page doi:10.1017/s0963548312000351 2012

  20. [20]

    What is the structure of K if K+K is small?Number Theory, 1240:109–134, 1987

    Gregory A Freiman. What is the structure of K if K+K is small?Number Theory, 1240:109–134, 1987

    work page 1987

  21. [21]

    Oded Goldreich and Leonid A. Levin. A hard-core predicate for all one-way functions. InProceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), pages 25–32, 1989.doi: 10.1145/73007.73010

    work page doi:10.1145/73007.73010 1989

  22. [22]

    PhD thesis, California Institute of Technology, 1997.doi:10.7907/rzr7-dt72

    Daniel Gottesman.Stabilizer Codes and Quantum Error Correction. PhD thesis, California Institute of Technology, 1997.doi:10.7907/rzr7-dt72

    work page doi:10.7907/rzr7-dt72 1997

  23. [23]

    W. T. Gowers. A new proof of Szemer´ edi’s theorem for arithmetic progressions of length four. Geometric and Functional Analysis, 8(3):529–551, 1998.doi:10.1007/s000390050065

    work page doi:10.1007/s000390050065 1998

  24. [24]

    W. T. Gowers, Ben Green, Freddie Manners, and Terence Tao. On a conjecture of Marton.Annals of Mathematics, 201(2):515–549, 2025.doi:10.4007/annals.2025.201.2.4

    work page doi:10.4007/annals.2025.201.2.4 2025

  25. [25]

    Finite field models in additive combinatorics

    Ben Green. Finite field models in additive combinatorics. InSurveys in combinatorics 2005, volume 327 ofLondon Math. Soc. Lecture Note Ser., pages 1–27. Cambridge Univ. Press, Cambridge, 2005. doi:10.1017/CBO9780511734885.002

    work page doi:10.1017/cbo9780511734885.002 2005

  26. [26]

    Notes on the polynomial Freiman–Ruzsa conjecture, 2005

    Ben Green. Notes on the polynomial Freiman–Ruzsa conjecture, 2005. Unpublished note. URL: https://people.maths.ox.ac.uk/greenbj/papers/PFR.pdf

    work page 2005

  27. [27]

    Montr´ eal notes on quadratic Fourier analysis

    Ben Green. Montr´ eal notes on quadratic Fourier analysis. InAdditive combinatorics, volume 43 of CRM Proc. Lecture Notes, pages 69–102. Amer. Math. Soc., Providence, RI, 2007.doi:10.1090/ crmp/043/06

    work page 2007

  28. [28]

    An inverse theorem for the GowersU 3(G) norm.Proceedings of the Edinburgh Mathematical Society, 51(1):73–153, 2 2008.doi:10.1017/S0013091505000325

    Ben Green and Terence Tao. An inverse theorem for the GowersU 3(G) norm.Proceedings of the Edinburgh Mathematical Society, 51(1):73–153, 2 2008.doi:10.1017/S0013091505000325

    work page doi:10.1017/s0013091505000325 2008

  29. [29]

    An equivalence between inverse sumset theorems and inverse con- jectures for theU 3 norm.Math

    Ben Green and Terence Tao. An equivalence between inverse sumset theorems and inverse con- jectures for theU 3 norm.Math. Proc. Cambridge Philos. Soc., 149(1):1–19, 2010.doi:10.1017/ S0305004110000186

    work page 2010

  30. [30]

    David Gross, Sepehr Nezami, and Michael Walter. Schur–Weyl duality for the clifford group with applications: Property testing, a robust Hudson theorem, and de Finetti representations.Commu- nications in Mathematical Physics, 385(3):1325–1393, 2021.doi:10.1007/s00220-021-04118-7

    work page doi:10.1007/s00220-021-04118-7 2021

  31. [31]

    The Weil representation in characteristic two.Adv

    Shamgar Gurevich and Ronny Hadani. The Weil representation in characteristic two.Adv. Math., 230(3):894–926, 2012.doi:10.1016/j.aim.2012.03.008. AN ALGORITHMIC POLYNOMIAL FREIMAN–RUZSA THEOREM 79

    work page doi:10.1016/j.aim.2012.03.008 2012

  32. [32]

    PhD thesis, Universit¨ at zu K¨ oln, 2021

    Markus Heinrich.On stabiliser techniques and their application to simulation and certification of quantum devices. PhD thesis, Universit¨ at zu K¨ oln, 2021. URL:http://kups.ub.uni-koeln.de/ 50465/

    work page 2021

  33. [33]

    Clifford testing: algorithms and lower bounds, 2025

    Marcel Hinsche, Zongbo Bao, Philippe van Dordrecht, Jens Eisert, Jop Bri¨ et, and Jonas Helsen. Clifford testing: algorithms and lower bounds, 2025. To appear in STOC’26. Available at arXiv/2510.07164

    work page arXiv 2025

  34. [34]

    Cubic Goldreich-Levin

    Dain Kim, Anqi Li, and Jonathan Tidor. Cubic Goldreich-Levin. InProceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4846–4892. SIAM, Philadelphia, PA, 2023.doi:10.1137/1.9781611977554.ch178

    work page doi:10.1137/1.9781611977554.ch178 2023

  35. [35]

    Equivalence of polynomial conjectures in additive combinatorics.Combinatorica, 32(5):607–618, 2012.doi:10.1007/s00493-012-2714-z

    Shachar Lovett. Equivalence of polynomial conjectures in additive combinatorics.Combinatorica, 32(5):607–618, 2012.doi:10.1007/s00493-012-2714-z

    work page doi:10.1007/s00493-012-2714-z 2012

  36. [36]

    Number 6 in Graduate Surveys

    Shachar Lovett.An Exposition of Sanders’ Quasi-Polynomial Freiman-Ruzsa Theorem. Number 6 in Graduate Surveys. Theory of Computing Library, 2015.doi:10.4086/toc.gs.2015.006

    work page doi:10.4086/toc.gs.2015.006 2015

  37. [37]

    Omnipredicting single-index models with multi-index models

    Saeed Mehraban and Mehrdad Tahmasbi. Improved bounds for testing low stabilizer complexity states. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, page 1222–1233. Association for Computing Machinery, 2025.doi:10.1145/3717823.3718228

    work page doi:10.1145/3717823.3718228 2025

  38. [38]

    Cam- bridge university press, 2010

    Michael A Nielsen and Isaac L Chuang.Quantum computation and quantum information. Cam- bridge university press, 2010

    work page 2010

  39. [39]

    An analog of Freiman’s theorem in groups.Ast´ erisque, 258(199):323–326, 1999

    Imre Ruzsa. An analog of Freiman’s theorem in groups.Ast´ erisque, 258(199):323–326, 1999

    work page 1999

  40. [40]

    Low-degree tests at large distances

    Alex Samorodnitsky. Low-degree tests at large distances. InProceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC ’07, page 506–515. Association for Computing Machinery, 2007.doi:10.1145/1250790.1250864

    work page doi:10.1145/1250790.1250864 2007

  41. [41]

    On the Bogolyubov-Ruzsa lemma.Analysis & PDE, 5(3):627–655, 2012.doi:10

    Tom Sanders. On the Bogolyubov-Ruzsa lemma.Analysis & PDE, 5(3):627–655, 2012.doi:10. 2140/apde.2012.5.627

    work page 2012

  42. [42]

    Cambridge University Press, 2006

    Terence Tao and Van H Vu.Additive combinatorics, volume 105. Cambridge University Press, 2006

    work page 2006

  43. [43]

    The inverse conjecture for the Gowers norm over finite fields in low characteristic.Annals of Combinatorics, 16(1):121–188, 2012.doi:10.1007/s00026-012-0129-0

    Terence Tao and Tamar Ziegler. The inverse conjecture for the Gowers norm over finite fields in low characteristic.Annals of Combinatorics, 16(1):121–188, 2012.doi:10.1007/s00026-012-0129-0

    work page doi:10.1007/s00026-012-0129-0 2012

  44. [44]

    Quadratic Goldreich–Levin theorems.SIAM Journal on Comput- ing, 43(2):730–766, 2014.doi:10.1137/12086827X

    Madhur Tulsiani and Julia Wolf. Quadratic Goldreich–Levin theorems.SIAM Journal on Comput- ing, 43(2):730–766, 2014.doi:10.1137/12086827X

    work page doi:10.1137/12086827x 2014

  45. [45]

    Classical simulation of quantum computation, the Gottesman-Knill theo- rem, and slightly beyond.Quantum Information and Computation, 10(3):258–271, March 2010

    Maarten Van Den Nest. Classical simulation of quantum computation, the Gottesman-Knill theo- rem, and slightly beyond.Quantum Information and Computation, 10(3):258–271, March 2010

    work page 2010

  46. [46]

    From affine to two-source extractors via approximate duality

    Noga Zewi and Eli Ben-Sasson. From affine to two-source extractors via approximate duality. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC ’11, page 177–186. Association for Computing Machinery, 2011.doi:10.1145/1993636.1993661. 80 D. CASTRO-SILVA, J. BRI ¨ET, S. ARUNACHALAM, A. DUTT, AND T. GUR Department of Computer ...

    work page doi:10.1145/1993636.1993661 2011