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.
