Raz (2009) proved that multilinear formulas computing the determinant of a generic n × n matrix require size n^{Ω(log n)}. A fundamental question in understanding this lower bound is identifying which structural properties of the determinant drive this hardness. Is it the quadratic number of variables? The dense connectivity? Specific algebraic symmetries? We establish that density is not essential. We prove the existence of n × n symbolic matrices with only Θ(nlog⁶ n) nonzero entries - reducing the variable count by a factor of n/log⁶ n - such that any multilinear formula computing their determinants still requires size n^{Ω(log n)}. 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.

Submodular functions are known to satisfy various forms of fractional subadditivity. This work investigates the conditions for equality to hold exactly or approximately in the fractional sub additivity of sub modular functions. We establish that a small gap in the inequality implies that the function is close to being modular, and that the gap is zero if and only if the function is modular. We then present natural implications of these results for special cases of sub modular functions, such as entropy, relative entropy, and matroid rank. As a consequence, we characterize the necessary and sufficient conditions for equality to hold in Shearer's lemma, recovering a result of Ellis et al. (2016) as a special case. We leverage our results to propose a new multivariate mutual information, which generalizes Watanabe's total correlation (1960), Han's dual total correlation (1975), and Csiszar and Narayan's shared information (2004), and analyze its properties. Among these properties, we extend Watanabe's characterization of total correlation as the maximum correlation over partitions to fractional partitions. When applied to matrix determinantal inequalities for positive definite matrices, our results recover the equality conditions of the classical determinantal inequalities of Hadamard, Szász, and Fischer as special cases.

Recently, Forbes, Kumar and Saptharishi [CCC, 2016] proved that there exists an explicit $d^{O(1)}$-variate and degree $d$ polynomial $P_{d}\in VNP$ such that if any depth four circuit $C$ of bounded formal degree $d$ which computes a polynomial of bounded individual degree $O(1)$, that is functionally equivalent to $P_d$, then $C$ must have size $2^{Ω(\sqrt{d}\log{d})}$. The motivation for their work comes from Boolean Circuit Complexity. Based on a characterization for $ACC^0$ circuits by Yao [FOCS, 1985] and Beigel and Tarui [CC, 1994], Forbes, Kumar and Saptharishi [CCC, 2016] observed that functions in $ACC^0$ can also be computed by algebraic $Σ\mathord{\wedge}ΣΠ$ circuits (i.e., circuits of the form -- sums of powers of polynomials) of $2^{\log^{O(1)}n}$ size. Thus they argued that a $2^{ω(\log^{O(1)}{n})}$ "functional" lower bound for an explicit polynomial $Q$ against $Σ\mathord{\wedge}ΣΠ$ circuits would imply a lower bound for the "corresponding Boolean function" of $Q$ against non-uniform $ACC^0$. In their work, they ask if their lower bound be extended to $Σ\mathord{\wedge}ΣΠ$ circuits. In this paper, for large integers $n$ and $d$ such that $ω(\log^2n)\leq d\leq n^{0.01}$, we show that any $Σ\mathord{\wedge}ΣΠ$ circuit of bounded individual degree at most $O\left(\frac{d}{k^2}\right)$ that functionally computes Iterated Matrix Multiplication polynomial $IMM_{n,d}$ ($\in VP$) over $\{0,1\}^{n^2d}$ must have size $n^{Ω(k)}$. Since Iterated Matrix Multiplication $IMM_{n,d}$ over $\{0,1\}^{n^2d}$ is functionally in $GapL$, improvement of the afore mentioned lower bound to hold for quasipolynomially large values of individual degree would imply a fine-grained separation of $ACC^0$ from $GapL$.

In this paper, we are interested in understanding the complexity of computing multilinear polynomials using depth four circuits in which polynomial computed at every node has a bound on the individual degree of r (referred to as multi-r-ic circuits). The goal of this study is to make progress towards proving superpolynomial lower bounds for general depth four circuits computing multilinear polynomials, by proving better and better bounds as the value of r increases. Recently, Kayal, Saha and Tavenas (Theory of Computing, 2018) showed that any depth four arithmetic circuit of bounded individual degree r computing a multilinear polynomial on n^O(1) variables and degree d=o(n), must have size at least (n/r^1.1)^Ω(√{d/r}) when r is o(d) and is strictly less than n^1.1. This bound however deteriorates with increasing r. It is a natural question to ask if we can prove a bound that does not deteriorate with increasing r or a bound that holds for a larger regime of r. We here prove a lower bound which does not deteriorate with r, however for a specific instance of d = d(n) but for a wider range of r. Formally, we show that there exists an explicit polynomial on n^O(1) variables and degree Θ(log² n) such that any depth four circuit of bounded individual degree r

Tavenas (Proceedings of mathematical foundations of computer science (MFCS), 2013) has recently proved that any $$n^{O(1)}$$ -variate and degree n polynomial in $$\mathsf {VP}$$ can be computed by a depth-4 $$\Sigma \Pi \Sigma \Pi $$ circuit of size $$2^{O(\sqrt{n}\log n)}$$ . So, to prove $$\mathsf {VP}\ne \mathsf {VNP}$$ it is sufficient to show that an explicit polynomial in $$\mathsf {VNP}$$ of degree n requires $$2^{\omega (\sqrt{n}\log n)}$$ size depth-4 circuits. Soon after Tavenas’ result, for two different explicit polynomials, depth-4 circuit-size lower bounds of $$2^{\Omega (\sqrt{n}\log n)}$$ have been proved (see Kayal et al. in Proceedings of symposium on theory of computing, ACM, 2014b. http://doi.acm.org/10.1145/2591796.2591847 ; Fournier et al. in Proceedings of symposium on theory of computing, ACM, 2014). In particular, using a combinatorial design Kayal et al. (2014b) construct an explicit polynomial in $$\mathsf {VNP}$$ that requires depth-4 circuits of size $$2^{\Omega (\sqrt{n}\log n)}$$ and Fournier et al. (Proceedings of symposium on theory of computing, ACM, 2014) show that the iterated matrix multiplication polynomial (which is in $$\mathsf {VP}$$ ) also requires $$2^{\Omega (\sqrt{n}\log n)}$$ size depth-4 circuits. In this paper, we identify a simple combinatorial property such that any polynomial f that satisfies this property would achieve a similar depth-4 circuit-size lower bound. In particular, it does not matter whether f is in $$\mathsf {VP}$$ or in $$\mathsf {VNP}$$ . As a result, we get a simple unified lower-bound analysis for the above-mentioned polynomials. Another goal of this paper is to compare our current knowledge of the depth-4 circuit-size lower bounds and the determinantal complexity lower bounds. Currently, the best known determinantal complexity lower bound is $$\Omega (n^2)$$ for permanent of a $$n\times n$$ matrix (which is a $$n^2$$ -variate and degree n polynomial) due to Cai et al. (Proceedings of symposium on theory of computing, ACM, 2008). We prove that the determinantal complexity of the iterated matrix multiplication polynomial is $$\Omega (dn)$$ where d is the number of matrices and n is the dimension of the matrices. In particular, our result settles the determinantal complexity of the iterated matrix multiplication polynomial to $$\Theta (dn)$$ . To the best of our knowledge, a $$\Theta (n)$$ bound for the determinantal complexity for the iterated matrix multiplication polynomial was known only for any constant $$d>1$$ , due to Jansen (Theory Comput Syst 49(2):343–354, 2011).

The complexity of Iterated Matrix Multiplication (IMM) is a central theme in Computational Complexity theory, as the problem is closely related to the problem of separating various complexity classes within ${P}$. In this paper, we study the algebraic formula complexity of multiplying $d$ many $2\times 2$ matrices, denoted ${IMM}_{d}$, and show that the well-known divide-and-conquer algorithm cannot be significantly improved at any depth as long as the formulas are multilinear. Formally, for each depth $\Delta \leq \log d$, we show that any product-depth $\Delta$ multilinear formula for ${IMM}_d$ must have size $\exp(\Omega(\Delta d^{1/\Delta})).$ It also follows from this that any multilinear circuit of product-depth $\Delta$ for the same polynomial of the above form must have a size of $\exp(\Omega(d^{1/\Delta})).$ In particular, any polynomial-sized multilinear formula for ${IMM}_d$ must have depth $\Omega(\log d)$, and any polynomial-sized multilinear circuit for ${IMM}_d$ must have depth $\Omega(\log d/\log \log d).$ Both of these bounds are tight up to constant factors. Our lower bound has the following three consequences for multilinear formula complexity. 1. Depth-reduction: A well-known result of Brent [ J. ACM, 21 (1974), pp. 201--206] implies that any formula of size $s$ can be converted to one of size $s^{O(1)}$ and depth $O(\log s)$; further, this reduction continues to hold for multilinear formulas. On the other hand, our lower bound implies that any depth-reduction in the multilinear setting cannot reduce the depth to $o(\log s)$ without a superpolynomial blow-up in size. 2. Circuits vs. formulas: Any circuit of size $s$ and product-depth $\Delta$ can be converted into a formula of product-depth $\Delta$ and size $s^{O(\Delta)}$. In the multilinear setting, we show that it is not possible to improve on this significantly for small depths. Formally, our results imply that for all large enough $s$ and $\Delta = o(\log s/\log \log s)$, there is an explicit multilinear polynomial $P_{s,\Delta}$ that has a syntactic multilinear circuit of size $s$ and is such that any multilinear formula of product-depth $\Delta$ computing $P_{s,\Delta}$ must have size $s^{\Omega(\Delta)}$. 3. Separations from general formulas: Shpilka and Yehudayoff [ Found. Trends Theor. Comput. Sci., 5 (2010), pp. 207--388] asked whether general formulas can be more efficient than multilinear formulas for computing multilinear polynomials. Our result, along with a nontrivial upper bound for ${IMM}_{d}$ implied by a result of Gupta et al. [SIAM J. Comput., 45 (2016), pp. 1064--1079], shows that for any size $s$ and product-depth $\Delta = o(\log s),$ general formulas of size $s$ and product-depth $\Delta$ cannot be converted to multilinear formulas of size $s^{O(1)}$ and product-depth $\Delta$ when the underlying field has characteristic zero.

We study the size blow-up that is necessary to convert an algebraic circuit of product-depth Δ + 1 to one of product-depth Δ in the multilinear setting. We show that for every positive Δ = Δ(n) = o(log n/log log n), there is an explicit multilinear polynomial P(Δ) on n variables that can be computed by a multilinear formula of product-depth Δ + 1 and size O(n), but not by any multilinear circuit of product-depth Δ and size less than exp(nΩ(1/Δ)). This result is tight up to the constant implicit in the double exponent for all Δ = o(log n/log log n). This strengthens a result of Raz and Yehudayoff (Computational Complexity 2009) who prove a quasipolynomial separation for constant-depth multilinear circuits, and a result of Kayal, Nair and Saha (STACS 2016) who give an exponential separation in the case Δ = 1. Our separating examples may be viewed as algebraic analogues of variants of the Graph Reachability problem studied by Chen, Oliveira, Servedio and Tan (STOC 2016), who used them to prove lower bounds for constant-depth Boolean circuits.

We show explicit separations between the expressive powers of multilinear formulas of small-depth and all polynomial sizes. Formally, for any s = s(n) = n^{O(1)} and any delta>0, we construct explicit families of multilinear polynomials P_n in F[x_1,...,x_n] that have multilinear formulas of size s and depth three but no multilinear formulas of size s^{1/2-delta} and depth o(log n/log log n). As far as we know, this is the first such result for an algebraic model of computation. Our proof can be viewed as a derandomization of a lower bound technique of Raz (JACM 2009) using epsilon-biased spaces.