Low-degree tests at large distances
zbMATH Open1232.68175arXivmath/0604353MaRDI QIDQ3549650FDOQ3549650
Authors: Alex Samorodnitsky 
Publication date: 5 January 2009
Full work available at URL: https://arxiv.org/abs/math/0604353
Recommendations
Boolean functionproperty testingReed-Muller codeerror probabilityprobabilistically checkable proofsGowers uniformity normgeneralized averagenumber of querieslow-degree testshypergraph linearity testsrepresentability by a low-degree polynomial over a finite field
Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Arithmetic combinatorics; higher degree uniformity (11B30) Error probability in coding theory (94B70)
Cited In (37)
- Additive combinatorics: with a view towards computer science and cryptography -- an exposition
- A generalization of a theorem of Rothschild and van Lint
- General systems of linear forms: equidistribution and true complexity
- Breaking the ε-Soundness Bound of the Linearity Test over GF(2)
- An additive combinatorics approach relating rank to communication complexity
- An inverse theorem for the uniformity seminorms associated with the action of \(\mathbb F_p^\infty\)
- Quadratic Goldreich-Levin theorems
- Finite field models in arithmetic combinatorics -- ten years on
- Query-efficient dictatorship testing with perfect completeness
- Some recent results on local testing of sparse linear codes
- The inverse conjecture for the Gowers norm over finite fields in low characteristic
- Optimal computational split-state non-malleable codes
- Linear forms and higher-degree uniformity for functions on \(\mathbb F^n_p\)
- Approximately symmetric forms far from being exactly symmetric
- A novel GPU-based implementation of the cube attack
- Quadratic Goldreich-Levin theorems
- An inverse theorem for the Gowers \(U^{s+1}[N]\)-norm
- Low Rate Is Insufficient for Local Testability
- Quantitative inverse theorem for Gowers uniformity norms \(\mathsf{U}^5\) and \(\mathsf{U}^6\) in \(\mathbb{F}_2^n\)
- Hard functions for low-degree polynomials over prime fields
- Non-Malleable Codes from Additive Combinatorics
- The structure theory of set addition revisited
- Non-classical polynomials and the inverse theorem
- Limits on the Rate of Locally Testable Affine-Invariant Codes
- A bilinear Bogolyubov-Ruzsa lemma with poly-logarithmic bounds
- Further cryptographic properties of the multiplicative inverse function
- Hard functions for low-degree polynomials over prime fields
- Large values of the Gowers-Host-Kra seminorms
- New bounds for Szemerédi's theorem. III: A polylogarithmic bound for \(r_{4}(n)\)
- Approximate cohomology
- A high dimensional Goldreich-Levin theorem
- LINEAR AND QUADRATIC UNIFORMITY OF THE MÖBIUS FUNCTION OVER
- Equivalence of polynomial conjectures in additive combinatorics
- Algebraic testing and weight distributions of codes.
- Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm
- A generalization of a theorem of Rothschild and van Lint
- Limitation on the Rate of Families of Locally Testable Codes
This page was built for publication: Low-degree tests at large distances
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3549650)
