Chattopadhyay, Arkadev ;
Datta, Rajit ;
Ghosal, Utsab ;
Mukhopadhyay, Partha
Monotone Complexity of Spanning Tree Polynomial ReVisited
Abstract
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 constantdegree 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_{n1,n}  ε⋅ ST_{n} and F_{n1,n} + ε⋅ ST_{n}, defined over (n1)n variables, have monotone circuit complexity 2^{Ω(n)} if ε ≥ 2^{ Ω(n)} and F_{n1,n} := ∏_{i = 2}ⁿ (x_{i,1} + ⋯ + x_{i,n}) is the complete setmultilinear polynomial. This provides the first εsensitive exponential lower bound for a family of polynomials inside VP. Enroute, we consider a problem in 2party, 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 nearlybalanced 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 (n1)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.
BibTeX  Entry
@InProceedings{chattopadhyay_et_al:LIPIcs.ITCS.2022.39,
author = {Chattopadhyay, Arkadev and Datta, Rajit and Ghosal, Utsab and Mukhopadhyay, Partha},
title = {{Monotone Complexity of Spanning Tree Polynomial ReVisited}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {39:139:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772174},
ISSN = {18688969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15635},
URN = {urn:nbn:de:0030drops156356},
doi = {10.4230/LIPIcs.ITCS.2022.39},
annote = {Keywords: Spanning Tree Polynomial, Monotone Computation, Lower Bounds, Communication Complexity}
}
25.01.2022
Keywords: 

Spanning Tree Polynomial, Monotone Computation, Lower Bounds, Communication Complexity 
Seminar: 

13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Issue date: 

2022 
Date of publication: 

25.01.2022 