Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR20-191 | 27th December 2020 13:16

Negations Provide Strongly Exponential Savings

RSS-Feed




TR20-191
Authors: Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay
Publication: 27th December 2020 13:30
Downloads: 794
Keywords: 


Abstract:

We show that there is a family of monotone multilinear polynomials over $n$ variables in VP, such that any monotone arithmetic circuit for it would be of size $2^{\Omega(n)}$. Before our result, strongly exponential lower bounds on the size of monotone circuits were known only for computing explicit polynomials in VNP. The family of polynomials we prescribe are the spanning tree polynomials, also considered by Jerrum and Snir (JACM,1982), but this time defined over constant-degree expander graphs.



ISSN 1433-8092 | Imprint