Monotone Complexity of Spanning Tree Polynomial Re-visited

09/14/2021
by   Arkadev Chattopadhyay, et al.
0

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 the 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 (Gashkov-Sergeev'12, Raz-Yehudayoff'11, Srinivasan'20, Cavalar-Kumar-Rossman'20, Hrubes-Yehudayoff'21). Recently, Hrubes'20 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). We consider the spanning tree polynomial ST_n defined over the complete graph on n vertices and show that the polynomials F_n-1,n - ϵ· ST_n and F_n-1,n + ϵ· ST_n defined over n^2 variables, have monotone circuit complexity 2^Ω(n) if ϵ≥ 2^-Ω(n) and F_n-1,n = ∏_i=2^n (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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset

Sign in with Google

×

Use your Google Account to sign in to DeepAI

×

Consider DeepAI Pro