Strongly Exponential Separation between Monotone VP and Monotone VNP

DOI10.1145/3417758MaRDI QIDQ5862285zbMATH OpenOpenAlexWikidataFDO

Authors Srikanth Srinivasan

Publication date 7 March 2022

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.01630

zbMATH Keywords

algebraic circuitsexpander graphsmonotone circuitsmultipartition communication complexity

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Communication complexity, information complexity (68Q11)

Abstract: We show that there is a sequence of explicit multilinear polynomials $P_n(x_1,ldots,x_n)inmathbbR[x_1,ldots,x_n]$ with non-negative coefficients that lies in monotone VNP such that any monotone algebraic circuit for $P_n$ must have size $exp(Omega(n)).$ This builds on (and strengthens) a result of Yehudayoff (2018) who showed a lower bound of $exp(ildeOmega(sqrtn)).$

Recommendations

• Separating monotone VP and VNP
• V-monotone independence
• scientific article; zbMATH DE number 934585
• Characterization of strong exponential dichotomies
• Strongly exponentially separated linear systems
• scientific article; zbMATH DE number 940746
• Separation of the monotone NC hierarchy
• Strongly exponential lower bounds for monotone computation
• On an exponential inequality and a strong law of large numbers for monotone measures
• A note on the monotonicity of \(V_{n}\)

Cited in

(9)

• Separation of the monotone NC hierarchy
• Log-concavity and lower bounds for arithmetic circuits
• Monotone arithmetic complexity of graph homomorphism polynomials
• Monotone classes beyond VNP
• Monotone classes beyond VNP
• On approximate symmetric polynomials and tightness of homogenization results
• Monotone bounded-depth complexity of homomorphism polynomials
• \textsf{VNP} = \textsf{VP} in the multilinear world
• Monotone separations for constant degree polynomials

This page was built for publication: Strongly Exponential Separation between Monotone VP and Monotone VNP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5862285)