Please use this identifier to cite or link to this item: http://hdl.handle.net/10263/7298
Title: Boolean Function Approximation by a Flat Polynomial
Authors: Gupta, Ankit
Keywords: Boolean functions
Polynomial
Fourier analysis
Issue Date: Jul-2021
Publisher: Indian Statistical Institute, Kolkata.
Citation: 33p.
Series/Report no.: Dissertation;M.Tech(CS)
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.
Description: Dissertation under the supervision Prof. Sourav Chakraborty
URI: http://hdl.handle.net/10263/7298
Appears in Collections:Dissertations - M Tech (CS)

Files in This Item:
File Description SizeFormat 
Ankit_Gupta_CS-19-21.pdf750.4 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.