Room 327

Discrete geometric methods in polynomial approximations of Boolean functions

Vaibhav Krishan

IMSc

(Note: change of date, and change of venue)

Polynomial approximations of Boolean functions is a vast area, with applications to complexity theory, algorithm design, cryptography, quantum computation, etc. We study two different frameworks of approximating Boolean functions by polynomials. In particular, we look at torus polynomials, introduced by Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019), with the goal of resolving a long-standing conjecture, by Barrington, about Boolean circuits.

We develop a method, extending the already well-established and widely successful method of dual polynomials, to prove lower bounds against the degree of torus polynomials approximating some Boolean function. Using this method, we prove a lower bound against torus polynomials approximating the AND function. This result nearly matches the known upper bound, and is the first lower bound result against torus polynomials.

We also develop this method in the case of symmetric torus polynomials, invariant under permutation of variables. Using methods from discrete geometry, we prove a nearly tight lower bound against symmetric torus polynomials approximating the AND function, and many other functions. This subsumes a similar result by Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019), where their result was for the MAJORITY function.

We develop the method further for torus polynomials, with the aim to prove lower bounds against torus polynomials approximating the MAJORITY function. This leads us again to a discrete geometric problem. We make a conjecture that, if true, would resolve Barrington's conjecture.