Strongly Exponential Separation between Monotone VP and Monotone VNP

Srinivasan, S

Srinivasan, S (corresponding author), Indian Inst Technol, Bombay, Maharashtra, India.; Srinivasan, S (corresponding author), Indian Inst Technol, Dept Math, Mumbai 400076, Maharashtra, India.

ACM TRANSACTIONS ON COMPUTATION THEORY, 2020; 12 (4):

Abstract

We show that there is a sequence of explicit multilinear polynomials P-n (x(1),..., x(n)) is an element of R[x(1),..., x(n)] with non-negative coeffic......

Full Text Link