Towards understanding the approximation of Boolean functions by nonclassical polynomials
Description
TitleTowards understanding the approximation of Boolean functions by nonclassical polynomials
Date Created2020
Other Date2020-05 (degree)
Extent1 online resource (viii, 104 pages)
DescriptionThe representation and approximation of Boolean functions by polynomials is an important area of research in theoretical computer science, having numerous applications in circuit complexity, communication complexity, pseudorandomness, quantum computation, learning theory, algorithm design, and explicit combinatorial constructions.
Results of Green and Tao (2009), Lovett et al. (2011), and Tao and Ziegler (2012), on the Inverse Conjecture for the Gowers norm over finite fields of low characteristic, and the subsequent work of Bhowmick and Lovett (2015), suggest that a potential barrier to the resolution of some of the outstanding open problems in this area is the class of nonclassical polynomials and its ability to nontrivially represent and approximate Boolean functions.
Motivated by these works, in this dissertation, we investigate the ability of nonclassical polynomials to approximate Boolean functions with respect to both previously studied and new notions of approximation:
• We introduce and study an agreement-based notion of approximation by polynomials over Z/2k Z. Investigating this notion serves as a proxy for understanding the maximum possible agreement between nonclassical polynomials and Boolean functions. We prove several new results that shed light on this new notion of approximation, and these results help us answer some questions left open in the
work of Bhowmick and Lovett (2015) concerning the approximation of Boolean
functions by nonclassical polynomials in the agreement sense.
• We propose a new notion of point-wise approximation by nonclassical polynomials. Using a result of Green et al. (1992), which itself is an extension of the classic work of Beigel and Tarui (1991), we observe that Boolean functions computable by ACC0 circuits (constant-depth circuits of polynomial size, containing AND, OR, NOT, and MODq gates) are amenable to point-wise approximation by low-degree nonclassical polynomials. Motivated by this new observation, we then explore how well can low-degree nonclassical polynomials point-wise approximate the majority function, in the hope of resolving the longstanding open problem of proving that majority is not computable by ACC0 circuits.
Our results suggest several interesting and promising directions of research. We ex-
plore some of these directions and state concrete open problems along with plausible
approaches to solving them.
NotePh.D.
NoteIncludes bibliographical references
Genretheses, ETD doctoral
LanguageEnglish
CollectionSchool of Graduate Studies Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.
Statistical Profile