In this SuperUROP project, I plan to investigate the problem of representing Boolean functions as real linear combinations of polynomials over the field {0,1} of degree 2 or higher. In particular, the aim of the project will be to find explicit functions that lack sparse (i.e., of polynomial size) representations in this setting, as well as to improve the currently known lower bounds for functions such as the AND function.

I decided to participate in SuperUROP to gain research experience and explore new research paths in my major. As a double major in Mathematics and EECS, this project will allow me to combine my interests in Analysis and TCS and build on my current exposure on Fourier analysis through courses I’ve taken on measure theory and functional analysis.