Paper Info
Title
Improved Optimal Testing Results from Global Hypercontractivity
Abstract
The problem of testing low-degree polynomials has received significant attention over the years due to its importance in theoretical computer science, and in particular in complexity theory. The problem is specified by three parameters: field size q, degree d and proximity parameter δ, and the goal is to design a tester making as few as possible queries to a given function, which is able to distinguish between the case the given function has degree at most d, and the case the given function is δ-far from any degree d function. With respect to these parameters, we say that a tester is optimal if it makes $O(q^{t}+1/\delta)$ queries, where $t=t(d,q)$ is the testing dimension of d, q (defined as the minimum integer so that for all $g:\mathbb{F}_{q}^{n}\rightarrow\mathbb{F}_{q}$ of degree more than d, there is a subspace of dimension t on which their restriction has degree exceeding d). For the field of size q, such tester was first given by Bhattacharyya et al. for q = 2, and later by Haramaty et al. [7] for all prime powers q. In fact, they showed that the natural t-flat tester is an optimal tester for the Reed-Muller code, for an appropriate t. Here, the t-flat tester is the tester that picks a uniformly random affine subspace A of dimension t, and checks that $\operatorname{deg}(f|_{A})\leqslant d$. Their analysis proves that the dependency of the t-flat tester on δ and d is optimal, however the dependency on the field size, i.e. the hidden constant in the O, is a tower-type function in q. We improve the result of Haramaty et al., showing that the dependency on the field size is polynomial. Our technique also applies in the more general setting of lifted affine invariant codes, and gives the same polynomial dependency on the field size. This answers a problem raised in [6]. Our approach significantly deviates from the strategy taken in earlier works [2], [7], [6], and is based on studying the structure of the collection of erroneous subspaces, i.e. subspaces A such that f|A has degree greater than d. Towards this end, we observe that these sets are poorly expanding in the affine version of the Grassmann graph and use that to establish structural results on them via global hypercontractivity. We then use this structure to perform local correction on f.
Year
DOI
Venue
2022
10.1109/FOCS54457.2022.00017
2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)
Keywords
DocType
ISSN
Reed-Muller Code,Optimal Testing,Global Hypercontractivity,Analysis of Boolean functions
Conference
1523-8288
ISBN
Citations 
PageRank 
978-1-6654-5520-6
0
0.34
References 
Authors
9
2
Name
Order
Citations
PageRank
Tali Kaufman149938.33
Dor Minzer2366.60