Tata Institute of Fundamental Research

A superpolynomial lower bound against weighted homogeneous formulas

STCS Student Seminar
Speaker: Varun Ramanathan (TIFR)
Organiser: Varun Ramanathan
Date: Friday, 8 Mar 2024, 14:30 to 15:30
Venue: A-201 (STCS Seminar Room)

(Scan to add to calendar)
Abstract: 

On the path to proving lower bounds against general arithmetic/algebraic models of computation, a longstanding open problem is to construct explicit polynomials that are superpolynomially hard for arithmetic formulas. Even for the potentially weaker model of homogeneous formulas, we do not have such strong lower bounds. Recently, Fournier, Limaye, Srinivasan and Tavenas gave a superpolynomial lower bound against a related model of computation called weighted homogeneous formulas, thus getting us a little (or a lot?) closer to homogeneous formula lower bounds. The proof goes via a relatively simple application of the probabilistic method. We will try and understand this proof. There are no prerequisites, besides the vague notion of mathematical maturity.