Speakers
Description
Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha and Bhargav Thankey
Abstract: A recent breakthrough work of Limaye, Srinivasan, and Tavenas [FOCS 2021] proved superpolynomial lower bounds for low-depth arithmetic circuits via a “hardness escalation" approach: they proved lower bounds for low-depth set-multilinear circuits and then lifted the bounds to low-depth general circuits. In this work, we prove superpolynomial lower bounds for low-depth circuits by bypassing the hardness escalation, i.e., the set-multilinearization, step. As set-multilinearization comes with an exponential blow-up in circuit size, our direct proof opens up the possibility of proving an exponential lower bound for low-depth homogeneous circuits by evading a crucial bottleneck. Our bounds hold for the iterated matrix multiplication and the Nisan-Wigderson design polynomials. We also define a subclass of unrestricted depth homogeneous formulas which we call unique parse tree (UPT) formulas, and prove superpolynomial lower bounds for these. This significantly generalizes the superpolynomial lower bounds for regular formulas [Kayal-Saha-Saptharishi, STOC 2014], [Fournier-Limaye-Malod-Srinivasan, STOC 2014].