Boyapati V S S Pruthvi supervised by Dr. Suryajith Chillara received his Master of Science by Research in Computer Science Engineering (CSE). Here’s a summary of his research work on Multilinear Formula Lower Bounds for Sparse Determinants

Raz [Raz09] proved that multilinear formulas computing the determinant of a generic n × n matrix must have size n Ω(log n) . A natural question this raises is: which properties of the determinant are actually driving this hardness? The proof simultaneously exploits several features of the polynomial (the quadratic number of variables, dense connectivity of the underlying matrix, and various symmetries), and it is not apparent which of these are genuinely necessary. This thesis establishes that density is not necessary. We prove the existence of n × n symbolic matrices with only Θ(n log6 n) nonzero entries, a reduction in variable count by a factor of n/ log6 n relative to the full matrix, such that any multilinear formula computing their determinant still requires size n Ω(log n) . The construction is based on rectangle sampling from the complete bipartite graph Kn,n. The resulting sparse graph G simultaneously possesses a perfect matching (guaranteeing that the determinant is nonzero) and exhibits diagonal imbalance under random vertex permutations, a geometric property that turns out to be the engine behind factor imbalance in Raz’s partial derivatives method. The conclusion is that Raz’s technique extends to the sparse setting with no loss in the quality of the lower bound, and that the key driver of multilinear hardness for the determinant is an expansion-like combinatorial property of the variable set, not its size. The analysis relies on concentration inequalities for dependent random variables, in particular the read-k Cherno bound due to Gavinsky, Lovett, Saks, and Srinivasan [GLSS15]. Every result stated for the determinant holds equally for the permanent. 

July 2026