DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2017.12

On Polynomial Approximations Over Z/2^kZ*

Authors: Abhishek Bhrushundi, Prahladh Harsha, and Srikanth Srinivasan

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract

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.

Cite as

Abhishek Bhrushundi, Prahladh Harsha, and Srikanth Srinivasan. On Polynomial Approximations Over Z/2^kZ*. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 12:1-12:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bhrushundi_et_al:LIPIcs.STACS.2017.12,
  author =	{Bhrushundi, Abhishek and Harsha, Prahladh and Srinivasan, Srikanth},
  title =	{{On Polynomial Approximations Over Z/2^kZ*}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{12:1--12:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.12},
  URN =		{urn:nbn:de:0030-drops-70212},
  doi =		{10.4230/LIPIcs.STACS.2017.12},
  annote =	{Keywords: Polynomials over rings, Approximation by polynomials, Boolean functions, Non-classical polynomials}
}

Document

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.23

On Higher-Order Fourier Analysis over Non-Prime Fields

Authors: Arnab Bhattacharyya, Abhishek Bhowmick, and Chetan Gupta

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract

The celebrated Weil bound for character sums says that for any low-degree polynomial P and any additive character chi, either chi(P) is a constant function or it is distributed close to uniform. The goal of higher-order Fourier analysis is to understand the connection between the algebraic and analytic properties of polynomials (and functions, generally) at a more detailed level. For instance, what is the tradeoff between the equidistribution of chi(P) and its "structure"? Previously, most of the work in this area was over fields of prime order. We extend the tools of higher-order Fourier analysis to analyze functions over general finite fields. Let K be a field extension of a prime finite field F_p. Our technical results are: 1. If P: K^n -> K is a polynomial of degree <= d, and E[chi(P(x))] > |K|^{-s} for some s > 0 and non-trivial additive character chi, then P is a function of O_{d, s}(1) many non-classical polynomials of weight degree < d. The definition of non-classical polynomials over non-prime fields is one of the contributions of this work. 2. Suppose K and F are of bounded order, and let H be an affine subspace of K^n. Then, if P: K^n -> K is a polynomial of degree d that is sufficiently regular, then (P(x): x in H) is distributed almost as uniformly as possible subject to constraints imposed by the degree of P. Such a theorem was previously known for H an affine subspace over a prime field. The tools of higher-order Fourier analysis have found use in different areas of computer science, including list decoding, algorithmic decomposition and testing. Using our new results, we revisit some of these areas. (i) For any fixed finite field K, we show that the list decoding radius of the generalized Reed Muller code over K equals the minimum distance of the code. (ii) For any fixed finite field K, we give a polynomial time algorithm to decide whether a given polynomial P: K^n -> K can be decomposed as a particular composition of lesser degree polynomials. (iii) For any fixed finite field K, we prove that all locally characterized affine-invariant properties of functions f: K^n -> K are testable with one-sided error.

Cite as

Arnab Bhattacharyya, Abhishek Bhowmick, and Chetan Gupta. On Higher-Order Fourier Analysis over Non-Prime Fields. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 23:1-23:29, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bhattacharyya_et_al:LIPIcs.APPROX-RANDOM.2016.23,
  author =	{Bhattacharyya, Arnab and Bhowmick, Abhishek and Gupta, Chetan},
  title =	{{On Higher-Order Fourier Analysis over Non-Prime Fields}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{23:1--23:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.23},
  URN =		{urn:nbn:de:0030-drops-66463},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.23},
  annote =	{Keywords: finite fields, higher order fourier analysis, coding theory, property testing}
}

Document

DOI: 10.4230/LIPIcs.CCC.2015.72

Nonclassical Polynomials as a Barrier to Polynomial Lower Bounds

Authors: Abhishek Bhowmick and Shachar Lovett

Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)

Abstract

The problem of constructing explicit functions which cannot be approximated by low degree polynomials has been extensively studied in computational complexity, motivated by applications in circuit lower bounds, pseudo-randomness, constructions of Ramsey graphs and locally decodable codes. Still, most of the known lower bounds become trivial for polynomials of super-logarithmic degree. Here, we suggest a new barrier explaining this phenomenon. We show that many of the existing lower bound proof techniques extend to nonclassical polynomials, an extension of classical polynomials which arose in higher order Fourier analysis. Moreover, these techniques are tight for nonclassical polynomials of logarithmic degree.

Cite as

Abhishek Bhowmick and Shachar Lovett. Nonclassical Polynomials as a Barrier to Polynomial Lower Bounds. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 72-87, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{bhowmick_et_al:LIPIcs.CCC.2015.72,
  author =	{Bhowmick, Abhishek and Lovett, Shachar},
  title =	{{Nonclassical Polynomials as a Barrier to Polynomial Lower Bounds}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{72--87},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{Zuckerman, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.72},
  URN =		{urn:nbn:de:0030-drops-50491},
  doi =		{10.4230/LIPIcs.CCC.2015.72},
  annote =	{Keywords: nonclassical polynomials, polynomials, lower bounds, barrier}
}

3 Search Results for "Bhowmick, Abhishek"

On Polynomial Approximations Over Z/2^kZ*

Abstract

Cite as

On Higher-Order Fourier Analysis over Non-Prime Fields

Abstract

Cite as

Nonclassical Polynomials as a Barrier to Polynomial Lower Bounds

Abstract

Cite as

Thanks for your feedback!

Could not send message