A superpolynomial lower bound against weighted homogeneous formulas

Varun Ramanathan
Varun Ramanathan
Friday, 8 Mar 2024, 14:30 to 15:30
A-201 (STCS Seminar Room)

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.