Monotone Complexity of Spanning Tree Polynomial Re-Visited

We prove two results that shed new light on the monotone complexity of the spanning tree polynomial, a classic polynomial in algebraic complexity and beyond. First, we show that the spanning tree polynomials having n variables and defined over constant-degree expander graphs, have monotone arithmetic complexity 2^{Ω(n)}. This yields the first strongly exponential lower bound on monotone arithmetic circuit complexity for a polynomial in VP. Before this result, strongly exponential size monotone lower bounds were known only for explicit polynomials in VNP [S. B. Gashkov and I. S. Sergeev, 2012; Ran Raz and Amir Yehudayoff, 2011; Srikanth Srinivasan, 2020; Bruno Pasqualotto Cavalar et al., 2020; Pavel Hrubeš and Amir Yehudayoff, 2021]. Recently, Hrubeš [Pavel Hrubeš, 2020] initiated a program to prove lower bounds against general arithmetic circuits by proving ε-sensitive lower bounds for monotone arithmetic circuits for a specific range of values for ε ∈ (0,1). The first ε-sensitive lower bound was just proved for a family of polynomials inside VNP by Chattopadhyay, Datta and Mukhopadhyay [Arkadev Chattopadhyay et al., 2021]. We consider the spanning tree polynomial ST_n defined over the complete graph of n vertices and show that the polynomials F_{n-1,n} - ε⋅ ST_{n} and F_{n-1,n} + ε⋅ ST_{n}, defined over (n-1)n variables, have monotone circuit complexity 2^{Ω(n)} if ε ≥ 2^{- Ω(n)} and F_{n-1,n} := ∏_{i = 2}ⁿ (x_{i,1} + ⋯ + x_{i,n}) is the complete set-multilinear polynomial. This provides the first ε-sensitive exponential lower bound for a family of polynomials inside VP. En-route, we consider a problem in 2-party, best partition communication complexity of deciding whether two sets of oriented edges distributed among Alice and Bob form a spanning tree or not. We prove that there exists a fixed distribution, under which the problem has low discrepancy with respect to every nearly-balanced partition. This result could be of interest beyond algebraic complexity. Our two results, thus, are incomparable generalizations of the well known result by Jerrum and Snir [Mark Jerrum and Marc Snir, 1982] which showed that the spanning tree polynomial, defined over complete graphs with n vertices (so the number of variables is (n-1)n), has monotone complexity 2^{Ω(n)}. In particular, the first result is an optimal lower bound and the second result can be thought of as a robust version of the earlier monotone lower bound for the spanning tree polynomial.