Low-degree tests at large distances

We define tests of boolean functions which distinguish between linear (or quadratic) polynomials, and functions which are very far, in an appropriate sense, from these polynomials. The tests have optimal or nearly optimal trade-offs between soundness and the number of queries. A central step in our analysis of quadraticity tests is the proof of aninverse theorem for the third Gowers uniformity norm of boolean functions. The last result implies that it ispossible to estimate efficiently the distance from the second-order Reed-Muller code on inputs lying far beyond its list-decoding radius. Our main technical tools are Fourier analysis on Z2n and methods from additive number theory. We observe that these methods can be used to give a tight analysis of the Abelian Homomorphism testing problemfor some families of groups, including powers of Zp.

• Publication year

  2006

• Venue

  Symposium on the Theory of Computing

• Publication date

  2006-04-16

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/1250790.1250864arXiv math/0604353
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• AN INVERSE THEOREM FOR THE GOWERS $U^3(G)$ NORM

  2008cited by this paper
• Montréal notes on quadratic Fourier analysis

  2007cited by this paper
• Near-optimal algorithms for unique games

  2006cited by this paper
• Gowers uniformity, influence of variables, and PCPs

  2005cited by this paper
• An inverse theorem for the Gowers U^3 norm

  2005cited by this paper
• Nonconventional ergodic averages and nilmanifolds

  2005cited by this paper
• Approximating - Outperforming a Random Assignment with Almost a Linear Factor

  2005cited by this paper
• Universal characteristic factors and Furstenberg averages

  2004cited by this paper
• The primes contain arbitrarily long arithmetic progressions

  2004cited by this paper
• Testing Low-Degree Polynomials over GF(2(

  2003influential reference
• Towards optimal lower bounds for clique and chromatic number

  2003cited by this paper
• Locally testable codes and PCPs of almost-linear length

  2002cited by this paper
• On the power of unique 2-prover 1-round games

  2002cited by this paper
• A new proof of Szemerédi's theorem

  2001cited by this paper
• A PCP characterization of NP with optimal amortized query complexity

  2000influential reference
• Recycling queries in PCPs and in linearity tests (extended abstract)

  1998cited by this paper
• Parallel Approximation Algorithms by Positive Linear Programming

  1998cited by this paper
• Probabilistic checking of proofs: a new characterization of NP

  1998cited by this paper
• Linearity testing in characteristic two

  1995cited by this paper
• Matroid theory

  1992cited by this paper
• Proof verification and hardness of approximation problems

  1992cited by this paper
• Self-testing/correcting with applications to numerical problems

  1990cited by this paper
• A hard-core predicate for all one-way functions

  1989cited by this paper
• The influence of variables on Boolean functions

  1988cited by this paper
• A class of multiple-error-correcting codes and the decoding scheme

  1954cited by this paper
• Theory of Error-correcting Codes

  year unknowncited by this paper

• Classical and Quantum Polynomial Freiman-Ruzsa Algorithms

  2026cites this paper
• The Gowers U3 norm of five classes of power permutations

  2026cites this paper
• A near-optimal Quadratic Goldreich-Levin algorithm

  2025cites this paper
• The Gowers U3 norm of one family of cubic power permutations

  2025cites this paper
• Homomorphism Testing with Resilience to Online Manipulations

  2025cites this paper
• Improved Bounds for the Freiman-Ruzsa Theorem

  2025cites this paper
• Clifford testing: algorithms and lower bounds

  2025cites this paper
• A General Framework for Low Soundness Homomorphism Testing

  2025cites this paper
• Algorithmic Polynomial Freiman-Ruzsa Theorems

  2025cites this paper
• Improved Bounds for Testing Low Stabilizer Complexity States

  2024cites this paper
• Polynomial-Time Tolerant Testing Stabilizer States

  2024influential citation
• Recognizing Sumsets is NP-Complete

  2024cites this paper
• On Optimal Testing of Linearity

  2024cites this paper
• Testing Sumsets is Hard

  2024cites this paper
• Marton’s conjecture in abelian groups with bounded torsion

  2024cites this paper
• Tolerant Testing of Stabilizer States with a Polynomial Gap via a Generalized Uncertainty Relation

  2024cites this paper
• On a conjecture of Marton

  2023influential citation
• Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach

  2023cites this paper
• Property Testing with Online Adversaries

  2023cites this paper
• Finite field models in arithmetic combinatorics -- twenty years on

  2023cites this paper
• A Study of Sparse Representation of Boolean Functions

  2023cites this paper
• A High Dimensional Goldreich-Levin Theorem

  2023cites this paper
• Quadratic Lower Bounds on the Approximate Stabilizer Rank: A Probabilistic Approach

  2023cites this paper
• Sumsets and entropy revisited

  2023influential citation
• Non-Malleable Code in the Split-State Model

  2022cites this paper
• Further Cryptographic Properties of the Multiplicative Inverse Function

  2022cites this paper
• Quantitative inverse theorem for Gowers uniformity norms $\mathsf {U}^5$ and $\mathsf {U}^6$ in $\mathbb {F}_2^n$

  2022cites this paper
• Parallel Repetition for the GHZ Game: Exponential Decay

  2022cites this paper
• Cubic Goldreich-Levin

  2022cites this paper
• Approximately symmetric forms far from being exactly symmetric

  2021cites this paper
• Cubic Goldreich-Levin SPUR+ Final Paper, Summer 2021

  2021cites this paper
• A Generalization of a Theorem of Rothschild and van Lint

  2021cites this paper
• The inverse theorem for the $U^3$ Gowers uniformity norm on arbitrary finite abelian groups: Fourier-analytic and ergodic approaches

  2021influential citation
• Sublinear-Time Computation in the Presence of Online Erasures

  2021cites this paper
• Non-classical polynomials and the inverse theorem

  2021cites this paper
• Sublinear-Time Computation in the Presence of An Online Adversary

  2021cites this paper
• Towards understanding the approximation of Boolean functions by nonclassical polynomials

  2020cites this paper
• Higher-order Fourier Analysis and Applications

  2019influential citation
• Approximate Local Decoding of Cubic Reed-Muller Codes Beyond the List Decoding Radius

  2018cites this paper
• A bilinear Bogolyubov-Ruzsa lemma with poly-logarithmic bounds

  2018cites this paper
• New bounds for Szemer\'edi's theorem, III: A polylogarithmic bound for $r_4(N)$

  2017cites this paper
• Additive Combinatorics and its Applications in Theoretical Computer Science

  2017cites this paper
• Linear and quadratic uniformity of the M\"obius function over $\mathbb{F}_q[t]$

  2017cites this paper
• Appoximate Cohomology

  2017cites this paper
• Approximate cohomology

  2017cites this paper
• A Novel GPU-Based Implementation of the Cube Attack - Preliminary Results Against Trivium

  2017cites this paper
• Revisiting the Sanders-Freiman-Ruzsa Theorem in $\mathbb{F}_p^n$ and its Application to Non-malleable Codes

  2016cites this paper
• The Fourier structure of low degree polynomials

  2016cites this paper
• REVISITING THE SANDERS-FREIMAN-RUZSA THEOREM IN Fp AND ITS APPLICATION TO NON-MALLEABLE CODES

  2016cites this paper
• Optimal Computational Split-state Non-malleable Codes

  2016cites this paper
• Revisiting the Sanders-Bogolyubov-Ruzsa theorem in Fpn and its application to non-malleable codes

  2016cites this paper
• An Application of Fourier analysis on Boolean functions in Theoretical Computer Science

  2016cites this paper
• Structure theorems in additive combinatorics

  2015cites this paper
• An Exposition of Sanders' Quasi-Polynomial Freiman-Ruzsa Theorem

  2015cites this paper
• Finite field models in arithmetic combinatorics - ten years on

  2015cites this paper
• Approximate algebraic structure

  2014influential citation
• J. (2015). Finite field models in arithmetic combinatorics – ten years on. Finite Fields and Their Applications , 32 , 233-274.

  2014cites this paper
• Additive combinatorics methods in computational complexity

  2014influential citation
• General systems of linear forms: equidistribution and true complexity

  2014cites this paper
• Non-malleable codes from additive combinatorics

  2014influential citation
• The polynomial Freiman-Ruzsa conjecture

  2014cites this paper
• Linear equations in primes and dynamics of nilmanifolds

  2014cites this paper
• Carries, Group Theory, and Additive Combinatorics

  2013cites this paper
• Introduction to Additive Combinatorics Taught Course Centre 2013

  2013cites this paper
• A Complete Bibliography of The Bell System Technical Journal , 1960 – 1969

  2013cites this paper
• Towards an optimal query efficient PCP?

  2013cites this paper
• Additive Combinatorics: With a View Towards Computer Science and Cryptography - An Exposition

  2013cites this paper
• Algorithmic regularity for polynomials and applications

  2013cites this paper
• Estimating the Gowers Norm of Modulo Functions over Prime Fields

  2012cites this paper
• The structure theory of set addition revisited

  2012cites this paper
• Final Report on New Developments in Symmetric Key Cryptanalysis

  2012cites this paper
• Analysis of Boolean Functions

  2012cites this paper
• An Additive Combinatorics Approach Relating Rank to Communication Complexity

  2012cites this paper
• Higher Order Fourier Analysis

  2012cites this paper
• Sampling-Based Proofs of Almost-Periodicity Results and Algorithmic Applications

  2012cites this paper
• Testability of linear-invariant properties

  2011cites this paper
• Probabilistically Checkable Proofs and Codes

  2011cites this paper
• The Inverse Conjecture for the Gowers Norm over Finite Fields in Low Characteristic

  2011cites this paper
• Hard Functions for Low-Degree Polynomials over Prime Fields

  2011cites this paper
• Algebraic Property Testing

  2011cites this paper
• Limits on the Rate of Locally Testable Affine-Invariant Codes

  2011cites this paper
• A Canonical Form for Testing Boolean Function Properties

  2011cites this paper
• Framework for Testing Linear-Invariant Properties

  2011cites this paper
• Additive combinatorics with a view towards computer science and cryptography: An exposition

  2011cites this paper
• Quadratic Goldreich-Levin Theorems

  2011influential citation
• An Inverse Theorem for the Uniformity Seminorms Associated with the Action of F

  2010cites this paper
• Breaking the epsilon-Soundness Bound of the Linearity Test over Gf(2)

  2010cites this paper
• A Fourier-Analytic Approach to Reed–Muller Decoding

  2010influential citation
• A Unified Framework for Testing Linear-Invariant Properties

  2010cites this paper
• Local list-decoding and testing of random linear codes from high error

  2010influential citation
• Limitation on the Rate of Families of Locally Testable Codes

  2010cites this paper
• Some Recent Results on Local Testing of Sparse Linear Codes

  2010cites this paper
• Query-Efficient Dictatorship Testing with Perfect Completeness

  2010cites this paper
• Equivalence of polynomial conjectures in additive combinatorics

  2010influential citation
• On the Bogolyubov–Ruzsa lemma

  2010influential citation
• Title : An Inverse Theorem for the Uniformity Seminorms Associated with the Action of

  2010cites this paper
• Large values of the Gowers-Host-Kra seminorms

  2010cites this paper
• On some microlocal properties of the range of a pseudo-differential operator of principal type

  2010cites this paper
• Linear Forms and Higher-Degree Uniformity for Functions On $${\mathbb{F}^{n}_{p}}$$

  2010influential citation
• Pseudorandomness In Computer Science and In Additive Combinatorics

  2010cites this paper