2026-07-23T05:17:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7021 2024-03-06T10:39:08Z ddc:004 open_access

On Polynomial Approximations Over Z/2^kZ* Bhrushundi, Abhishek Harsha, Prahladh Srinivasan, Srikanth Polynomials over rings Approximation by polynomials Boolean functions Non-classical polynomials 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Abhishek Bhrushundi and Prahladh Harsha and Srikanth Srinivasan 2017 Is Part Of LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2017.12 urn:nbn:de:0030-drops-70212 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.12 eng https://creativecommons.org/licenses/by/3.0/legalcode