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 | Size | Format | |
---|---|---|---|---|
Ankit_Gupta_CS-19-21.pdf | 750.4 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.