scientific article
From MaRDI portal
Publication:3549650
zbMath1232.68175arXivmath/0604353MaRDI QIDQ3549650
Publication date: 5 January 2009
Full work available at URL: https://arxiv.org/abs/math/0604353
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Reed-Muller codeBoolean functionprobabilistically checkable proofserror probabilityproperty testingGowers 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) Error probability in coding theory (94B70) Arithmetic combinatorics; higher degree uniformity (11B30)
Related Items
A bilinear Bogolyubov-Ruzsa lemma with poly-logarithmic bounds, Approximately symmetric forms far from being exactly symmetric, Non-classical polynomials and the inverse theorem, An inverse theorem for the uniformity seminorms associated with the action of \(\mathbb F_p^\infty\), Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm, Large values of the Gowers-Host-Kra seminorms, Equivalence of polynomial conjectures in additive combinatorics, Approximate cohomology, Linear forms and higher-degree uniformity for functions on \(\mathbb F^n_p\), NEW BOUNDS FOR SZEMERÉDI'S THEOREM, III: A POLYLOGARITHMIC BOUND FOR, The inverse conjecture for the Gowers norm over finite fields in low characteristic, An inverse theorem for the Gowers \(U^{s+1}[N\)-norm], Breaking the ε-Soundness Bound of the Linearity Test over GF(2), Non-Malleable Codes from Additive Combinatorics, The structure theory of set addition revisited, Limitation on the Rate of Families of Locally Testable Codes, Query-Efficient Dictatorship Testing with Perfect Completeness, Some Recent Results on Local Testing of Sparse Linear Codes, Optimal Computational Split-state Non-malleable Codes, Finite field models in arithmetic combinatorics -- ten years on, General systems of linear forms: equidistribution and true complexity, A generalization of a theorem of Rothschild and van Lint, A generalization of a theorem of Rothschild and van Lint, Limits on the Rate of Locally Testable Affine-Invariant Codes, Further cryptographic properties of the multiplicative inverse function, LINEAR AND QUADRATIC UNIFORMITY OF THE MÖBIUS FUNCTION OVER, Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition, An Additive Combinatorics Approach Relating Rank to Communication Complexity
