Alladi Ramakrishnan Hall

Topics in Correlation Bounds

Sankardeep Chakaborty

IMSc

Polynomials over GF(2) are an important and well studied mathematical object in complexity theory as they form one of the most basic models of computation, in particular they correspond to depth-2 unbounded fan-in circuits whose output gate is a sum (in our case, modulo 2). A very natural and fundamental question is to study the computational power of this model. This thesis surveys some topic in correlation bounds which provides one possible approach for studying this sort of questions. Specifically we will see up to what extent we can approximate the given function by low degree and high degree polynomials. Along the way we mention how techniques from additive combinatorics and property testing play an important role in proving such correlation bounds.