• with Sagnik Dutta and Nitin Saxena
  • ACM Trans. Comput. Theory, TOCT 2024 (preliminary version - MFCS 2022)
  • awarded Best Student Paper at MFCS 2022

PDF

We show that any product-depth algebraic circuit for the Iterated Matrix Multiplication polynomial (when ) must be of size at least where is the golden ratio. This improves the recent breakthrough result of Limaye, Srinivasan, and Tavenas (FOCS’21), who showed a super polynomial lower bound of the form for constant-depth circuits.

One crucial idea of the (LST21) result was to use set-multilinear polynomials where each set in the variables’ underlying partition could be of different sizes. By picking the set sizes more carefully (depending on the depth we are working with), we first show that any product-depth set-multilinear circuit for (when ) needs size at least . This improves the lower bound of (LST21). We then use their Hardness Escalation technique to lift this to general circuits.

We also show that these techniques cannot improve our lower bound significantly. For the specific two set sizes used in (LST21), they showed that their lower bound cannot be improved. We show that for any set sizes (out of maximum possible ), the scope for improving our lower bound is minuscule. There exists a set-multilinear circuit that has product-depth and size almost matching our lower bound such that the value of the measure used to prove the lower bound is maximum for this circuit. This results in a barrier to further improvement using the same measure.

Research overview