Pratyush Vempati’s (a third-year UG student working with Suryajith Chillara) paper- Multilinear Formula Lower Bounds for Sparse Determinants was accepted by the Computational Complexity Conference (CCC), a highly selective and topmost tier/flagship conference of Computational Complexity. Here is the summary of the research work as explained by the authors:

Raz (2009) proved that multilinear formulas computing the determinant of a generic nn matrix require size n(logn). A fundamental question in understanding this lower bound is identifying which structural properties of the determinant drive this hardness. In pursuit of this question, we prove the existence of nn symbolic matrices with only (nlog6n) nonzero entries—reducing the variable count by a factor of nlog6n —such that any multilinear formula computing their determinants still requires size n(logn). Our construction uses rectangle sampling from the complete bipartite graph to generate sparse matrices that simultaneously maintain perfect matchings (ensuring nonzero determinant) while exhibiting diagonal imbalance under random vertex permutations—a geometric property we identify as the key driver of factor imbalance in Raz’s framework.

This demonstrates that Raz’s partial derivatives method is remarkably robust to sparsification, and suggests that the fundamental source of multilinear hardness for determinant lies in expansion-like combinatorial structure rather than density. Our techniques combine concentration inequalities for dependent random variables with insights from random graph theory.

For more details: https://computationalcomplexity.org/Archive/2026/accepted_papers.html

https://eccc.weizmann.ac.il/report/2026/090/

July 2026