Pith. sign in

REVIEW 3 major objections 4 minor 34 references

Algorithmic Polynomial Freiman-Ruzsa Theorems

T0 review · 3 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The Polynomial Freiman-Ruzsa theorem is made algorithmic: a bounded-doubling set A⊆F_2^n yields a learnable subspace V, |V|≤|A|, covering A by K^C translates.

desk verdict First constructive PFR, worth a serious referee; the classical part leans on one unverified preprint and one under-specified final step, both fixable. read the letter →

arxiv 2509.02338 v1 pith:S3IH7E26 submitted 2025-09-02 math.CO

Srinivasan Arunachalam , Davi Castro-Silva , Arkopal Dutt , Tom Gur This is my paper · ORCID
classification math.CO MSC 11B3011B7568Q1268W20
keywords algorithmicPolynomialFreiman-RuzsaadditivecombinatoricsoverF_2^nsubspacecoveringquadraticGoldreich-LevinstabilizerstatesandGowersU^3normquantumalgorithmsdequantizationhomomorphismtestingquerylowerbounds
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Sets that only double under addition are known, by the Polynomial Freiman-Ruzsa theorem, to be coverable by few translates of a subspace no larger than the set. That theorem has been existential: extracting the subspace by brute force costs exponential time. This paper makes it constructive, proving that a basis for such a subspace can be learned in polynomial time from a tiny number of random samples and membership queries to the set, in both classical and quantum settings. The consequences are structural: local approximate linearity becomes testable and the affine map that explains it can be learned, and approximate homomorphisms admit efficiently computable decompositions. The gains hold even after accounting for matching (up to log factors) lower bounds on queries.

What carries the argument

The workhorse function is g(x,y)=1_S(x)(-1)^{f(x)·y}, built from a dense Freiman model S⊆F_2^m of A after a random linear projection; if A has small doubling, g is guaranteed to have large inner product with some quadratic phase (-1)^{q(x,y)}. That quadratic q is found by the quadratic Goldreich-Levin learner [BC25] classically, or by the stabilizer-state agnostic learner [CGYZ25] quantumly. Extracting the mixed second difference B(x,y)=q(x,y)-q(x,0)-q(0,y)+q(0,0) gives a matrix M with B(x,y)=y^T M x, and Fourier analysis upgrades the correlation to the conclusion f(x)=Mx+v on a constant fraction of the dense model; Ruzsa's covering lemma turns that into a cover of A by few translates of the

What would settle it

Run the quadratic Goldreich-Levin routine [BC25] on a known quadratic phase function for n from about 50 to 400 and compare the empirical scaling of query count and runtime with n^2 log n and n^3; if the observed growth exceeds the stated bounds by an unbounded factor, the classical PFR theorem loses its polynomial guarantee. Alternatively, search for a set A with |A+A|≤K|A| that requires more than K^C translates of any subspace of size at most |A| for every fixed C; such a set would refute the base PFR statement itself.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central claim is Theorem 4.1: for any A⊆F_2^n with |A+A|≤K|A|, a randomized algorithm draws O(log|A|+K) random elements from A, makes 2^{O(K)} log^2|A| log log|A| queries to the membership oracle of A, and runs in K^{O(log K)} n^4 log n time; with probability at least 2/3 it returns a basis for a subspace V of size at most |A| such that A is covered by P_1'(K) translates of V. A quantum version achieves O(n^3) time and 2^{O(K)} log|A| quantum queries. The paper also proves algorithmic homomorphism testing: any map f:F_2^m→F_2^n that satisfies f(x_1)+f(x_2)=f(x_3)+f(x_4) on at least 1/K of its additive quadruples is close in fractional Hamming distance to an affi

Load-bearing premise

The classical speed limits are inherited wholesale from the cited quadratic Goldreich-Levin subroutine [BC25], with the quantum results separately leaning on the cited stabilizer-state learner [CGYZ25]; if either runs slower than stated, the corresponding PFR algorithms slow down in lockstep.

Editorial extensions

If this is right

  • If A has constant doubling K, a basis for the covering subspace can be found in O(n^4 log n) classical time, so applications of PFR that currently need a non-constructive cover can in principle use explicit covers.
  • Homomorphism testing becomes effective: any map that is 1/K close to affine-linearity locally can be certified and its affine approximation learned, with consequences for property testing and coding settings.
  • The structured approximate homomorphism result gives an explicit decomposition f=g+h into a linear part and a small-image part whenever the derivative image is small.
  • The Ω(n^2) classical and Ω(n) quantum query lower bounds mean the query dependence on n is settled up to logarithmic factors, so further improvement must come from the K-dependence rather than from n.
  • Quantum algorithms save a factor n in time and a factor log n in queries, matching the known quantum-vs-classical gap for these learning tasks.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The K-dependence (2^{O(K)} queries and K^{O(log K)} time) is treated as constant in the asymptotic guarantees; an obvious next step, left open here, is a version whose complexity is polynomial in K, which would cover sets whose doubling constant grows slowly with n.
  • The sampling/localization plus dense-model pipeline is not obviously restricted to F_2: the same ingredients exist in other finite fields and abelian groups, so an analogous algorithmic PFR may hold wherever a quadratic Goldreich-Levin analogue exists.
  • If the dequantized quadratic Goldreich-Levin routine [BC25] were improved further, the entire classical O(n^4) bound would improve automatically; conversely, the lower-bound argument shows the overall route cannot be made subquadratic in n queries.
  • Applications that use PFR as a black box—such as sparsification algorithms or extractor constructions—could be re-examined with the explicit subspace in hand, potentially turning existence proofs into reductions with actual running time.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proves algorithmic versions of the Polynomial Freiman-Ruzsa theorem. For A ⊆ F_2^n with doubling constant K, it gives a classical randomized algorithm that, with O(log|A| + K) random samples and 2^{O(K)} log^2|A| log log|A| queries to A, outputs a basis for a subspace V of size at most |A| such that A is covered by K^C translates of V; it also gives a quantum algorithm with quadratically better query complexity. The proof strategy is to avoid algorithmizing the entropic proof of GGMT by instead going through a dense model / Freiman-isomorphism reduction, proving an algorithmic restricted-homomorphism lemma, and using quadratic Goldreich-Levin type learning (classically via Briet--Castro-Silva, quantumly via stabilizer-state learning). The paper also proves query lower bounds of Ω(n^2) classically and Ω(n) quantumly.

Significance. If correct, the paper resolves the natural algorithmic version of PFR: the covering subspace can be learned in polynomial time for constant K, with essentially optimal query dependence on n. The reduction from PFR to learning quadratic/stabilizer structure is conceptually clean and likely to be influential. The paper is transparent about its black-box reliance on recent external results, and the main theorems are explicitly stated with sample, query, and time complexity. However, the classical half is wholly dependent on the unverified preprint [BC25], and several technical steps in the proofs of the central lemma and the lower bounds need correction. The qualitative claims are likely salvageable, but the manuscript in its current form is not yet sound in all details.

major comments (3)
  1. [Lemma 3.4 / §3.4] The procedure for finding z0 does not meet its stated guarantee. With estimation error ε = 1/(128 P4(K)^3), the candidate z0 from Claim 3.6 has estimated agreement at least 1/(64P4^3) − ε = 1/(128P4^3); the empirical maximizer z* has estimate at least that, so the true agreement of z* is only bounded below by 0, not by 2^m/(128P4^3). To obtain the claimed P'_4 = 128P4^3, the estimation error would need to be at most 1/(256P4^3). Additionally, an empirical-probability estimate to error ε requires Θ(1/ε^2) samples, so the stated O(log(K)P4(K)^3) samples per candidate should be O(log(K)P4(K)^6), changing the total in Lemma 3.4 to P4(K)^9 rather than P4(K)^6. These are K-dependent factors and do not change the qualitative theorem, but the proof of this central lemma is not correct as written.
  2. [§5.1 and §5.2, Theorems 5.1/5.2] Fano's inequality is used in the wrong direction. For uniformly random H, Fano gives Pr[error] ≥ (H(H|H') − 1)/log|supp(H)|, hence Pr[success] ≤ (I(H:H') + 1)/log|supp(H)|. The manuscript instead writes Pr[identification] ≥ 1 − I/log|supp|, which would imply success probability near 1 for t = 0, contradicting the information-theoretic setup. With the correct inequality, the proofs can be repaired to give t = Ω(n^2) and t = Ω(n), but the displayed arguments as written are invalid.
  3. [§2.3, Theorem 2.12; used in Theorems 4.1, 4.3, 4.4] The classical results inherit all time and query bounds from [BC25]. The theorem as stated has O(n^3) time and n^2 log n log(1/δ)(1/ε)^{O(log 1/ε)} queries; for ε = 1/poly(n) the query count is super-polynomial in n, so the O(n^3) time cannot include oracle-query cost in the usual unit-cost oracle model. The authors should state explicitly whether 'time' excludes oracle queries and, if so, add the cost of processing each query in Lemma 3.4 and Theorem 4.1. Since [BC25] is a recent preprint by one of the present authors and is load-bearing for all classical claims, the authors should either supply a proof of the exact theorem they use or give a precise statement with consistent time/query accounting.
minor comments (4)
  1. [Theorem 2.4] The statement '|span(A)| ≤ 2^{2K/(2K)} · |A|' appears to be a typo; the proof later uses the standard bound |span(A)| ≤ 2^{2K}|A|. Please correct the displayed theorem.
  2. [Theorem 4.1 proof] The substitution K' = 2^{33}K^{13} appears to be off by a factor of 2: Claim 4.2 and the bound |A'| ≥ 2^m/(2^{11}K^4) give denominator 2^{34}K^{13}. The constants do not affect the qualitative result, but should be checked.
  3. [Throughout] All logarithms are implicitly base 2; please state this explicitly, since expressions like m = log|4A'| + 10 depend on the base.
  4. [§5] The paper claims random samples are information-theoretically necessary to hit a basis of A, but no formal sample lower bound is proved. The lower-bound section concerns queries; please clarify or move the sample-complexity remark to the discussion.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the classical and quantum algorithms are genuine reductions to stated external theorems (combinatorial PFR and quadratic Goldreich–Levin), with no equation-level reduction of the target to its inputs.

full rationale

The paper's derivation chain is a sequence of genuine reductions. Lemma 3.3 proves a combinatorial restricted homomorphism testing statement from the Balog–Szemerédi–Gowers theorem and the combinatorial PFR theorem (Theorem 1.1). Lemma 3.4 algorithmizes this by defining a function g, invoking the quadratic Goldreich–Levin theorem (Theorem 2.12) as an oracle for finding a correlated quadratic phase, and then converting that quadratic correlation into an affine approximation via explicit Fourier/Parseval arguments. The same structure is used in the quantum setting with the stabilizer learning theorem of Chen–Gong–Ye–Zhang (Theorem 2.9). The final algorithms (Theorems 4.1, 4.3, 4.4, 4.5) then combine these lemmas with localization and dense-model lemmas (Lemmas 3.1, 3.2) and Ruzsa's covering lemma. No equation is defined in terms of its own output, and no fitted parameter is renamed as a prediction. The paper does rely on [BC25], a preprint co-authored by one of the present authors, for the classical quadratic Goldreich–Levin theorem. This is a self-citation and it is load-bearing for the classical runtime bounds. However, [BC25] is an external, parameter-free theorem whose stated assumptions do not include algorithmic PFR; it is not derived in this paper, and its correctness is not assumed from the present paper's conclusions. Under the review rules, this is independent support and does not constitute circularity. The same applies to [CGYZ25], which is external. The limitation that a failure of [BC25]'s complexity bound would weaken the classical results is a correctness risk, not a circularity. The paper is self-contained relative to its cited combinatorial and learning-theoretic inputs, and the main algorithm is a novel combination of those inputs rather than a restatement of them.

Assumptions & free parameters 0 free parameters · 10 assumptions · 0 invented entities

The central claim rests on a stack of external theorems, mostly classical additive combinatorics and two recent learning algorithms. No number is fitted to data, and no new entity (particle, force, dimension) is introduced. The authors' own prior works ([AD25b], [AD25a], and [BC25] co-authored by Castro-Silva) are used as lemmas, but those lemmas do not assume the target algorithmic PFR result, so the circularity burden is limited to self-citation. The K-dependence of the output polynomials is inherited from [GGMT25], [BC25], and [CGYZ25] and is not optimized.

assumptions (10)
  • domain assumption Combinatorial PFR [GGMT25]: A with doubling K is covered by P_0(K) translates of a subspace V of size at most |A|.
    Used in Lemma 3.3 to cover the graph set Gamma' and start the restricted homomorphism testing argument.
  • standard math Balog-Szemeredi-Gowers theorem: E(A) >= |A|^3/K implies a large subset with doubling poly(K).
    Used in Lemma 3.3 to extract a small-doubling subset Gamma' from a high-energy graph.
  • standard math Freiman-Ruzsa span bound: |span(A)| <= 2^{2K}|A| for A subset of F_2^n.
    Controls the localization dimension m and the kernel size of pi in Theorem 4.1.
  • standard math Plunnecke's inequality: |4A| <= K^4|A|.
    Ensures m = log|A| + 4 log K + 10 satisfies the dense-model Lemma 3.2.
  • standard math Ruzsa's covering lemma.
    Converts a large intersection A cap V' into a cover by translates in Theorems 4.1 and 4.4.
  • standard math Stabilizer state structure theorem [Nes08].
    Represents learned stabilizer states as affine subspace plus quadratic and linear phases in Lemma 4.6.
  • domain assumption Agnostic stabilizer learning [CGYZ25] with the stated quasipolynomial-in-1/tau complexity.
    Quantum subroutine in Lemma 4.6: learns a stabilizer state with fidelity within epsilon of the optimum.
  • domain assumption Quadratic Goldreich-Levin [BC25] with time O(n^3) and query count n^2 log n (1/epsilon)^{O(log 1/epsilon)}.
    The dequantization tool powering all classical algorithms; its complexity claims are imported verbatim and are the weakest load-bearing external input.
  • standard math SWAP test and Clifford synthesis (Lemmas 2.10 and 2.11).
    Estimate fidelities and prepare quadratic phase states in the quantum algorithm.
  • standard math Fano's inequality, Holevo's theorem, and the count of subspaces of F_2^n being 2^{Theta(n^2)}.
    Information-theoretic lower bounds in Section 5.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Algorithmic Polynomial Freiman-Ruzsa Theorems." pith.science (2026). https://pith.science/paper/S3IH7E26

@misc{pith2026250902338,
  author       = {Pith},
  title        = {Pith review of: Algorithmic Polynomial Freiman-Ruzsa Theorems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/S3IH7E26}},
  note         = {Machine review of arXiv:2509.02338}
}
abstract

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 give classical and quantum polynomial-time algorithms that, for $A \subseteq \mathbb{F}_2^n$ with doubling constant $K$, learn an explicit description of a subspace $V \subseteq \mathbb{F}_2^n$ of size $|V| \leq |A|$ such that $A$ can be covered by $K^C$ translates of $V$, for a universal constant $C>1$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 30 canonical work pages

  1. [1]

    Learning stabilizer structure of quantum states, 2025

    Srinivasan Arunachalam and Arkopal Dutt. Learning stabilizer structure of quantum states, 2025. Manuscript

    work page 2025

  2. [2]

    Polynomial-time tolerant testing stabilizer states

    Srinivasan Arunachalam and Arkopal Dutt. Polynomial-time tolerant testing stabilizer states. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , STOC '25, page 1234–1241, New York, NY, USA, 2025. Association for Computing Machinery

    work page 2025

  3. [3]

    Non-malleable codes from additive combinatorics

    Divesh Aggarwal, Yevgeniy Dodis, and Shachar Lovett. Non-malleable codes from additive combinatorics. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing , STOC '14, page 774–783, New York, NY, USA, 2014. Association for Computing Machinery

    work page 2014

  4. [4]

    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. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2535--2567. SIAM, 2024

    work page 2024

  5. [5]

    Asadi, Alexander Golovnev, Tom Gur, and Igor Shinkar

    Vahid R. Asadi, Alexander Golovnev, Tom Gur, and Igor Shinkar. Worst-case to average-case reductions via additive combinatorics. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , STOC 2022, page 1566–1574, New York, NY, USA, 2022. Association for Computing Machinery

    work page 2022

  6. [6]

    A near-optimal Q uadratic G oldreich- L evin algorithm

    Jop Bri \"e t and Davi Castro-Silva . A near-optimal Q uadratic G oldreich- L evin algorithm. arXiv preprint arXiv:2505.13134 , 2025

    arXiv 2025

  7. [7]

    New bounds for matching vector families

    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, New York, NY, USA, 2013. Association for Computing Machinery

    work page 2013

  8. [8]

    Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa

    Benjamin Bedert, Tamio-Vesa Nakajima, Karolina Okrasa, and Stanislav Z ivn \`y . Strong sparsification for 1-in-3- SAT via P olynomial F reiman- R uzsa. arXiv preprint arXiv:2507.17878 , 2025

    work page Pith review arXiv 2025

Show all 34 references
  1. [9]

    An additive combinatorics approach relating rank to communication complexity

    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

    2014

  2. [10]

    Sampling-based proofs of almost-periodicity results and algorithmic applications

    Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, and Julia Wolf. Sampling-based proofs of almost-periodicity results and algorithmic applications. In International Colloquium on Automata, Languages, and Programming , pages 955--966. Springer, 2014

    2014

  3. [11]

    Tolerant testing of stabilizer states with a polynomial gap via a generalized uncertainty relation

    Zongbo Bao, Philippe van Dordrecht, and Jonas Helsen. Tolerant testing of stabilizer states with a polynomial gap via a generalized uncertainty relation. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , STOC '25, page 1254–1262, New York, NY, USA, 2025....

    2025

  4. [12]

    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. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , STOC '25, page 429–438, New York, NY, USA, 2025. Association f...

    2025

  5. [13]

    Elements of information theory

    Thomas M Cover. Elements of information theory . John Wiley & Sons, 1999

    1999

  6. [14]

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

    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

    2003

  7. [15]

    Quantum proofs for classical theorems

    Andrew Drucker and Ronald de Wolf. Quantum proofs for classical theorems. arXiv preprint arXiv:0910.3376 , 2009

    2009 arXiv

  8. [16]

    On sums of generating sets in Z _2^n

    Chaim Even-Zohar. On sums of generating sets in Z _2^n . Combinatorics, probability and computing , 21(6):916--941, Nov 2012

    2012

  9. [17]

    What is the structure of k if k+ k is small? Number Theory , page 109, 1987

    Gregory A Freiman. What is the structure of k if k+ k is small? Number Theory , page 109, 1987

    1987

  10. [18]

    On a conjecture of M arton

    William Timothy Gowers, Ben Green, Freddie Manners, and Terence Tao. On a conjecture of M arton. Annals of Mathematics , 201(2):515--549, 2025

    2025

  11. [19]

    Finite field models in additive combinatorics

    Ben Green. Finite field models in additive combinatorics. arXiv preprint math/0409420 , 2004

    2004 arXiv

  12. [20]

    Notes on the polynomial F reiman- R uzsa conjecture

    Ben Green. Notes on the polynomial F reiman- R uzsa conjecture . Available at https://people.maths.ox.ac.uk/greenbj/papers/PFR.pdf , 2004

    2004

  13. [21]

    Notes on the polynomial F reiman-- R uzsa conjecture

    Ben Green. Notes on the polynomial F reiman-- R uzsa conjecture. preprint , 2005

    2005

  14. [22]

    An equivalence between inverse sumset theorems and inverse conjectures for the u3 norm

    Ben Green and Terence Tao. An equivalence between inverse sumset theorems and inverse conjectures for the u3 norm. In Mathematical Proceedings of the Cambridge Philosophical Society , volume 149, pages 1--19. Cambridge University Press, 2010

    2010

  15. [23]

    Cubic G oldreich- L evin

    Dain Kim, Anqi Li, and Jonathan Tidor. Cubic G oldreich- L evin. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 4846--4892. SIAM, 2023

    2023

  16. [24]

    Equivalence of polynomial conjectures in additive combinatorics

    Shachar Lovett. Equivalence of polynomial conjectures in additive combinatorics. Combinatorica , 32(5):607--618, 2012

    2012

  17. [25]

    An exposition of S anders' quasi-polynomial F reiman- R uzsa theorem

    Shachar Lovett. An exposition of S anders' quasi-polynomial F reiman- R uzsa theorem. Theory of Computing , pages 1--14, 2015

    2015

  18. [26]

    The quantum query complexity of learning multilinear polynomials

    Ashley Montanaro. The quantum query complexity of learning multilinear polynomials. Information Processing Letters , 112(11):438--442, 2012

    2012

  19. [27]

    Improved bounds for testing low stabilizer complexity states

    Saeed Mehraban and Mehrdad Tahmasbi. Improved bounds for testing low stabilizer complexity states. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , STOC '25, page 1222–1233, New York, NY, USA, 2025. Association for Computing Machinery

    2025

  20. [28]

    Classical simulation of quantum computation, the G ottesman- K nill theorem, and slightly beyond

    M Nest. Classical simulation of quantum computation, the G ottesman- K nill theorem, and slightly beyond. arXiv preprint arXiv:0811.0898 , 2008

    2008 arXiv

  21. [29]

    Efficient synthesis of linear reversible circuits

    Ketan N Patel, Igor L Markov, and John P Hayes. Efficient synthesis of linear reversible circuits. arXiv preprint quant-ph/0302002 , 2003

    2003 arXiv

  22. [30]

    An analog of F reiman's theorem in groups

    Imre Ruzsa. An analog of F reiman's theorem in groups. Ast \'e risque , 258(199):323--326, 1999

    1999

  23. [31]

    Low-degree tests at large distances

    Alex Samorodnitsky. Low-degree tests at large distances. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing , STOC '07, page 506–515, New York, NY, USA, 2007. Association for Computing Machinery

    2007

  24. [32]

    Additive combinatorics , volume 105

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

    2006

  25. [33]

    Quadratic G oldreich-- L evin theorems

    Madhur Tulsiani and Julia Wolf. Quadratic G oldreich-- L evin theorems. SIAM Journal on Computing , 43(2):730--766, 2014

    2014

  26. [34]

    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, New York, NY, USA, 2011. Association for Computing Machinery

    2011

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.