Towards understanding the approximation of Boolean functions by nonclassical polynomials
Friday, April 17, 2020, 02:30pm - 04:00pm
Speaker: Abhishek Bhrushundi
Location : Remote via Webex
Swastik Kopparty (Chair), Eric Allender, Shubhangi Saraf, Hamed Hatami (external member - McGill University)
Event Type: PhD Defense
Abstract: The representation and approximation of Boolean functions by polynomials is an essential tool in theoretical computer science, having numerous applications in various areas including, but not limited to, circuit complexity, communication complexity, pseudorandomness, quantum computation, learning theory, algorithm design, and explicit combinatorial constructions. The refutation of the inverse conjecture of the Gowers norm by Green and Tao (2007), Lovett et al. (2008), and Tao and Ziegler (2011), and subsequent work of Bhowmick and Lovett (2014), all suggest that a barrier to the resolution of some of the outstanding open problems in the area is the existence of the class of nonclassical polynomials and their ability to represent and approximate Boolean functions. Motivated by these works, in this dissertation, we investigate the ability of nonclassical polynomials to approximate Boolean functions under both new and previously studied notions of approximation: • We introduce and study an agreement-based notion of approximation by polynomials over the ring of integers modulo powers of two. This notion serves as a proxy for understanding how well nonclassical polynomials can approximate Boolean functions in the agreement-sense. We prove several new results that shed light on this notion of approximation, answering questions left open in the work of Bhowmick and Lovett (2014). • We propose a new notion of point-wise approximation by nonclassical polynomials. Using a result of Green et al. (1992), which is an extension of the classic work of Beigel and Tarui (1991), we observe that under this notion, Boolean functions computable by ACC0 circuits (constant-depth circuits with AND, OR, NOT, and MOD gates) are amenable to approximation by low-degree nonclassical polynomials. Motivated by this new observation, we then explore the approximability of the majority and the delta functions by nonclassical polynomials in this point-wise sense, in the hope of resolving the long-standing open problem of showing that majority is not computable by ACC0 circuits. We also compare the two notions of approximation introduced by us to other standard notions, especially correlation-based approximation, listing several open problems and future directions of research.