Raz [JACM 2009] established that multilinear formulas computing the $n \times n$ determinant require size $n^{\Omega(\log n)}$, with subsequent superpolynomial lower bounds largely restricted to the determinant, permanent, or custom-engineered polynomials. We explore whether simpler yet more natural structures might exhibit similar hardness. We find that this is indeed the case. Specifically, there exist sparse symbolic matrices whose determinants retain $n^{\Omega(\log n)}$ multilinear formula hardness, even with only $\Theta(\log n)$ nonzero entries per row and column. By revisiting Raz's classical framework, we identify and address the probabilistic and structural challenges of adapting it to sparse settings using new sampling techniques, and concentration bounds for dependent variables.
(Joint work with Pruthvi Boyapati and Pratyush Vempati.)
Appeared in Proc. of CCC 2026.
Bio: Suryajith Chillara is an Assistant Professor at IIIT Hyderabad, working with the Center for Security, Theory and Algorithmic Research (CSTAR). His research primarily focuses on the intersection of Algorithms and Computational Complexity Theory. He completed his undergraduate studies at IIT Kanpur before earning his MSc and PhD in Computer Science from the Chennai Mathematical Institute. Prior to his current role, he held post-doctoral research positions at IIT Bombay and the University of Haifa.
