Boolean Function Approximation by a Flat Polynomial

Abstract

Boolean functions f : {−1, 1} n → {−1, 1} arise in many areas of theoretical computer science and mathematics, for example: complexity theory, quantum computing and graph theory etc and Fourier analysis is a powerful technique used to analyze problems in these areas. One of the most important and longstanding open problems in this field is the Fourier Entropy-Influence (FEI) conjecture [EG96], first formulated by Ehud Friedgut and Gil Kalai; The FEI conjecture connects two fundamental properties of boolean function f, i.e. influence and entropy. FEI conjecture says, for all boolean functions f : {−1, 1} n → {−1, 1}, H[ ˆf 2 ] ≤ CI[f] where H[ ˆf 2 ] is the spectral entropy of f and if we fix = 1 3 and consider polynomials p such that |p(x) − f(x)| ≤ 1 3 where f is boolean function then these polynomials have many applications in theoretical computer science. In particular, this work attempts to address the following problem: Suppose, the FEI conjecture is true, what can be said about the approximating polynomials. We have a flat polynomial of degree d and sparsity 2 ω(d) . The proposed conjecture [SSM+20] says that No flat polynomial of degree d and sparsity 2 ω(d) can 1 3− approximate a boolean function.[The degree of a function is the maximum d such that ˆf(S) 6= 0 for some set S of size d]. It is useful to understand better the structure of polynomials that −approximate Boolean functions on the Boolean cube. Such polynomials have proved to be powerful and found diverse applications in theoretical computer science. Here, we restrict ourselves to a class of polynomials called flat polynomials over {−1, 1}, i.e., polynomials whose non-zero coefficients have the same magnitude. This conjecture is true by assuming FEI conjecture and it is also true for a class of polynomials without assuming FEI conjecture.