Search

We study approximation of Boolean functions by low-degree polynomials over the ring Z/2^kZ. More precisely, given a Boolean function F:{0,1}^n -> {0,1}, define its k-lift to be F_k:{0,1}^n -> {0,2^(k-1)} by F_k(x) = 2^(k-F(x)) (mod 2^k). We consider the fractional agreement (which we refer to as \gamma_{d,k}(F)) of F_k with degree d polynomials from Z/2^kZ[x_1,..,x_n]. Our results are the following: * Increasing k can help: We observe that as k increases, gamma_{d,k}(F) cannot decrease. We give two kinds of examples where gamma_{d,k}(F) actually increases. The first is an infinite family of functions F such that gamma_{2d,2}(F) - gamma_{3d-1,1}(F) >= Omega(1). The second is an infinite family of functions F such that gamma_{d,1}(F) <= 1/2+o(1) - as small as possible - but gamma_{d,3}(F) >= 1/2 + Omega(1). * Increasing k doesn't always help: Adapting a proof of Green [Comput. Complexity, 9(1):16--38, 2000], we show that irrespective of the value of k, the Majority function Maj_n satisfies gamma_{d,k}(Maj_n) <= 1/2+ O(d)/sqrt{n}. In other words, polynomials over Z/2^kZ for large k do not approximate the majority function any better than polynomials over Z/2Z. We observe that the model we study subsumes the model of non-classical polynomials, in the sense that proving bounds in our model implies bounds on the agreement of non-classical polynomials with Boolean functions. In particular, our results answer questions raised by Bhowmick and Lovett [In Proc. 30th Computational Complexity Conf., pages 72-87, 2015] that ask whether non-classical polynomials approximate Boolean functions better than classical polynomials of the same degree.

We make progress on some questions related to polynomial approximations of AC^0. It is known, from the works of Tarui (Theoret. Comput. Sci. 1993) and Beigel, Reingold, and Spielman (Proc. 6th CCC 1991), that any AC^0 circuit of size s and depth d has an epsilon-error probabilistic polynomial over the reals of degree (log (s/epsilon))^{O(d)}. We improve this upper bound to (log s)^{O(d)}* log(1/epsilon), which is much better for small values of epsilon. We give an application of this result by using it to resolve a question posed by Tal (ECCC 2014): we show that (log s)^{O(d)}* log(1/epsilon)-wise independence fools AC^0, improving on Tal's strengthening of Braverman's theorem (J. ACM 2010) that (log (s/epsilon))^{O(d)}-wise independence fools AC^0. Up to the constant implicit in the O(d), our result is tight. As far as we know, this is the first PRG construction for AC^0 that achieves optimal dependence on the error epsilon. We also prove lower bounds on the best polynomial approximations to AC^0. We show that any polynomial approximating the OR function on n bits to a small constant error must have degree at least ~Omega(sqrt{log n}). This result improves exponentially on a recent lower bound demonstrated by Meka, Nguyen, and Vu (arXiv 2015).

We consider the following multiplication-based tests to check if a given function f: F^n_q -> F_q is the evaluation of a degree-d polynomial over F_q for q prime. Test_{e,k}: Pick P_1,...,P_k independent random degree-e polynomials and accept iff the function f P_1 ... P_k is the evaluation of a degree-(d + ek) polynomial. We prove the robust soundness of the above tests for large values of e, answering a question of Dinur and Guruswami (FOCS 2013). Previous soundness analyses of these tests were known only for the case when either e = 1 or k = 1. Even for the case k = 1 and e > 1, earlier soundness analyses were not robust. We also analyze a derandomized version of this test, where (for example) the polynomials P_1 ,... , P_k can be the same random polynomial P. This generalizes a result of Guruswami et al. (STOC 2014). One of the key ingredients that go into the proof of this robust soundness is an extension of the standard Schwartz-Zippel lemma over general finite fields F_q, which may be of independent interest.

In this paper, we address the question of whether the recent derandomization results obtained by the use of the low-degree long code can be extended to other product settings. We consider two settings: (1) the graph product results of Alon, Dinur, Friedgut and Sudakov [GAFA, 2004] and (2) the "majority is stablest" type of result obtained by Dinur, Mossel and Regev [SICOMP, 2009] and Dinur and Shinkar [In Proc. APPROX, 2010] while studying the hardness of approximate graph coloring. In our first result, we show that there exists a considerably smaller subgraph of K_3^{\otimes R} which exhibits the following property (shown for K_3^{\otimes R} by Alon et al.): independent sets close in size to the maximum independent set are well approximated by dictators. The "majority is stablest" type of result of Dinur et al. and Dinur and Shinkar shows that if there exist two sets of vertices A and B in K_3^{\otimes R} with very few edges with one endpoint in A and another in B, then it must be the case that the two sets A and B share a single influential coordinate. In our second result, we show that a similar "majority is stablest" statement holds good for a considerably smaller subgraph of K_3^{\otimes R}. Furthermore using this result, we give a more efficient reduction from Unique Games to the graph coloring problem, leading to improved hardness of approximation results for coloring.