Computer Science Seminar
Speaker: Vaibhav Krishnan, IIT Bombay
Date: Wednesday, 17 April 2024
Time: 3.30 PM
Venue: Lecture Hall 2
New Lower Bounds for Symmetric Boolean Functions
Vaibhav Krishnan
IIT Bombay.
17-04-24

---

Abstract

In this talk, I will talk about our recent work regarding torus polynomials approximating symmetric Boolean functions. Torus polynomials were introduced by Bhrushundi, Hosseini, Lovett and Rao in a paper presented at ITCS 2019, towards solving a 35 years old conjecture, that for a long time had no seemingly viable approach.

Torus polynomials fit into the framework of approximating Boolean functions by polynomials, where a torus polynomial approximates a Boolean function if it takes a value close to the function in its fractional part. Bhrushundi et al. used this approach to reduce the original conjecture to an algebraic conjecture about degree lower bounds against torus polynomials approximating the MAJORITY function (the function that outputs one if and only if ones are in the majority in the input).

Our contribution takes this a step further. The conjecture by Bhrushundi et al. is non-existential in nature, we convert it to an existence based conjecture. Then, we reduce it further to a seemingly more manageable conjecture regarding the L-2 norm of specific vectors. The crux of our work lies in constructing machinery, inspired by the method of dual polynomials, to establish lower bounds on the degree of torus polynomials approximating Boolean functions. Along the way, we prove several key results, a highlight of them is given below.

1. We prove that symmetric torus polynomials, polynomials that remain unchanged on permuting variables, are strictly weaker than their asymmetric counterparts. This is in contrast to previously studied polynomial approximations, where they have the same power for approximating symmetric functions.

2. We prove the first degree lower bound against asymmetric torus polynomials, which almost matches the degree upper bound, for the AND function.

3. We show that our method can also be used to prove upper bounds, by proving upper bounds for the majority function.

I will briefly describe our approach, and some open questions we propose.

This is a joint work with Prof. Sundar Vishwanathan, CSE IITB.

Speaker Bio: Vaibhav is a PhD scholar at CSE IITB, under the guidance of Prof. Sundar Vishwanathan and Prof. Nutan Limaye, where he has submitted his thesis. Before this, he completed his B. Tech. from CSE IITB in 2013.