We prove that any total boolean function of rank r can be computed by a deterministic communication protocol of complexity O(√r · log(r)). Similarly, any graph whose adjacency matrix has rank r has chromatic number at most 2O(√r·log(r)). This gives a nearly quadratic improvement in the dependence on the rank over previous results. © 2014 ACM.

Recently there has been much interest in Gowers uniformity norms from the perspective of theoretical computer science. This is mainly due to the fact that these norms provide a method for testing whether the maximum correlation of a function f : np → Fp with polynomials of degree at most d ≤ p is nonnegligible, while making only a constant number of queries to the function. This is an instance of correlation testing . In this framework, a fixed test is applied to a function, and the acceptance probability of the test is dependent on the correlation of the function from the property. This is an analogue of proximity oblivious testing, a notion coined by Goldreich and Ron, in the high error regime. In this work, we study general properties which are affine invariant and which are correlation testable using a constant number of queries. We show that any such property (as long as the field size is not too small) can in fact be tested by Gowers uniformity tests, and hence having correlation with the property is equivalent to having correlation with degree d polynomials for some fixed d. We stress that our result holds also for nonlinear properties which are affine invariant. This completely classifies affine invariant properties which are correlation testable. The proof is based on higher-order Fourier analysis. Another ingredient is a nontrivial extension of a graph theoretical theorem of Erd̈os, Lov́asz, and Spencer to the context of additive number theory. © 2014 Society for Industrial and Applied Mathematics.

The Polynomial Freiman-Ruzsa conjecture is one of the central open problems in additive combinatorics. If true, it would give tight quantitative bounds relating combinatorial and algebraic notions of approximate subgroups. In this note, we restrict our attention to subsets of Euclidean space. In this regime, the original conjecture considers approximate algebraic subgroups as the set of lattice points in a convex body. Green asked in 2007 whether this can be simplified to a generalized arithmetic progression, while not losing more than a polynomial factor in the underlying parameters. We give a negative answer to this question, based on a recent reverse Minkowski theorem combined with estimates for random lattices.

An approximate membership data structure is a randomized data structure representing a set which supports membership queries. It allows for a small false positive error rate but has no false negative errors. Such data structures were first introduced by Bloom in the 1970s and have since had numerous applications, mainly in distributed systems, database systems, and networks. The algorithm of Bloom (known as a Bloom filter) is quite effective: it can store an approximation of a set S of size n by using only ≈ 1.44n log2(1/ε) bits while having false positive error ε. This is within a constant factor of the information-theoretic lower bound of n log2(1/ε) for storing such sets. Closing this gap is an important open problem, as Bloom filters are widely used in situations where storage is at a premium. Bloom filters have another property: they are dynamic. That is, they support the iterative insertions of up to n elements. In fact, if one removes this requirement, there exist static data structures that receive the entire set at once and can almost achieve the information-theoretic lower bound; they require only (1 + o(1))n log2(1/ε) bits. Our main result is a new lower bound for the space requirements of any dynamic approximate membership data structure. We show that for any constant ε > 0, any such data structure that achieves false positive error rate of ε must use at least C(ε) · n log2(1/ε) memory bits, where C(ε) > 1 depends only on ε. This shows that the information-theoretic lower bound cannot be achieved by dynamic data structures for any constant error rate. © 2013 Society for Industrial and Applied Mathematics.

Let P be an affine invariant property of multivariate functions over a constant size finite field. We show that if P is locally testable with a constant number of queries, then one can estimate the distance of a function f from P with a constant number of queries. This was previously unknown even for simple properties such as cubic polynomials over the binary field. Our test is simple: Take a restriction of f to a constant dimensional affine subspace, and measure its distance from P. We show that by choosing the dimension large enough, this approximates with high probability the global distance of f from P. The analysis combines the approach of Fischer and Newman [SIAM J. Comp 2007] who established a similar result for graph properties, with recently developed tools in higher order Fourier analysis, in particular those developed in Bhattacharyya et al. [STOC 2013]. Copyright © 2013 by The Institute of Electrical and Electronics Engineers, Inc.

Suppose that you have n truly random bits x = (x1, . . ., xn) and you wish to use them to generate m n pseudorandom bits y = (y1, . . ., ym) using a local mapping, i.e., each yi should depend on at most d = O(1) bits of x. In the polynomial regime of m = ns, s > 1, the only known solution, originating from [Goldreich, Electronic Colloquium on Computational Complexity (ECCC), 2000], is based on random local functions: Compute yi by applying some fixed (public) d-ary predicate P to a random (public) tuple of distinct input indices (xi1 , . . ., xid). Our goal in this paper is to understand, for any value of s, how the pseudorandomness of the resulting sequence depends on the choice of the underlying predicate. We derive the following results: (1) We show that pseudorandomness against F2-linear adversaries (i.e., the distribution y has small bias) is achieved if the predicate is (a) k = Ω(s)-resilient, i.e., uncorrelated with any k-subset of its inputs, and (b) has algebraic degree of Ω(s) even after fixing Ω(s) of its inputs. We also show that these requirements are necessary, and so they form a tight characterization (up to constants) of security against linear attacks. Our positive result shows that a d-local small-biased generator can have output length of nΩ(d), answering an open question of Mossel, Shpilka, and Trevisan [Proceedings of FOCS, 2003]. Our negative result shows that a candidate for a pseudorandom generator proposed by Applebaum [Comput. Complexity, 25 (2016), pp. 667–722] and by O’Donnell and Witmer [Proceedings of CCC 2014] is insecure. We use similar techniques to refute a conjecture of Feldman, Perkins, and Vempala [Proceedings of STOC 2015] regarding the hardness of planted constraint satisfaction problems. (2) Motivated by the cryptanalysis literature, we consider security against algebraic attacks. We provide the first theoretical treatment of such attacks by formalizing a general notion of algebraic inversion and distinguishing attacks based on the polynomial calculus proof system. We show that algebraic attacks succeed if and only if the predicate P has rational degree e = Θ(s), where the rational degree of a predicate P is the smallest integer e for which there exist degree e polynomials Q, R, not both zero, such that PQ = R. As a corollary, we obtain the first example of a predicate P for which the generated sequence y passes all linear tests but fails to pass some polynomial-time computable test, answering an open question posed by Applebaum [Comput. Complexity, 25 (2016), pp. 667–722].

Let G be a finite Abelian group and A a subset of G. The spectrum of A is the set of its large Fourier coefficients. Known combinatorial results on the structure of spectrum, such as Chang's theorem, become trivial in the regime |A|=|G|α whenever α≤c, where c≥1/2 is some absolute constant. On the other hand, there are statistical results, which apply only to a noticeable fraction of the elements, which give nontrivial bounds even to much smaller sets. One such theorem (due to Bourgain) goes as follows. For a noticeable fraction of pairs γ1,γ2 in the spectrum, γ1+γ2 belongs to the spectrum of the same set with a smaller threshold. Here we show that this result can be made combinatorial by restricting to a large subset. That is, we show that for any set A there exists a large subset A′, such that the sumset of the spectrum of A′ has bounded size. Our results apply to sets of size |A|=|G|α for any constant α>0, and even in some sub-constant regime.