Bhrushundi, Abhishek ;
Harsha, Prahladh ;
Srinivasan, Srikanth
On Polynomial Approximations Over Z/2^kZ*
Abstract
We study approximation of Boolean functions by lowdegree polynomials over the ring Z/2^kZ. More precisely, given a Boolean function F:{0,1}^n > {0,1}, define its klift to be F_k:{0,1}^n > {0,2^(k1)} by F_k(x) = 2^(kF(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_{3d1,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):1638, 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 nonclassical polynomials, in the sense that proving bounds in our model implies bounds on the agreement of nonclassical polynomials with Boolean functions. In particular, our results answer questions raised by Bhowmick and Lovett [In Proc. 30th Computational Complexity Conf., pages 7287, 2015] that ask whether nonclassical polynomials approximate Boolean functions better than classical polynomials of the same degree.
BibTeX  Entry
@InProceedings{bhrushundi_et_al:LIPIcs:2017:7021,
author = {Abhishek Bhrushundi and Prahladh Harsha and Srikanth Srinivasan},
title = {{On Polynomial Approximations Over Z/2^kZ*}},
booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
pages = {12:112:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770286},
ISSN = {18688969},
year = {2017},
volume = {66},
editor = {Heribert Vollmer and Brigitte Vallée},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7021},
URN = {urn:nbn:de:0030drops70212},
doi = {10.4230/LIPIcs.STACS.2017.12},
annote = {Keywords: Polynomials over rings, Approximation by polynomials, Boolean functions, Nonclassical polynomials}
}
2017
Keywords: 

Polynomials over rings, Approximation by polynomials, Boolean functions, Nonclassical polynomials 
Seminar: 

34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Issue date: 

2017 
Date of publication: 

2017 