Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > VNP:
Reports tagged with VNP:
TR13-091 | 17th June 2013
Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi

A super-polynomial lower bound for regular arithmetic formulas.

We consider arithmetic formulas consisting of alternating layers of addition $(+)$ and multiplication $(\times)$ gates such that the fanin of all the gates in any fixed layer is the same. Such a formula $\Phi$ which additionally has the property that its formal/syntactic degree is at most twice the (total) degree ... more >>>


TR14-163 | 29th November 2014
Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh

Homomorphism polynomials complete for VP

The VP versus VNP question, introduced by Valiant, is probably the most important open question in algebraic complexity theory. Thanks to completeness results, a variant of this question, VBP versus VNP, can be succinctly restated as asking whether the permanent of a generic matrix can be written as a determinant ... more >>>


TR15-171 | 28th October 2015
Joshua Grochow

Monotone projection lower bounds from extended formulation lower bounds

Revisions: 2 , Comments: 1

In this short note, we show that the permanent is not complete for non-negative polynomials in $VNP_{\mathbb{R}}$ under monotone p-projections. In particular, we show that Hamilton Cycle polynomial and the cut polynomials are not monotone p-projections of the permanent. To prove this we introduce a new connection between monotone projections ... more >>>


TR16-038 | 15th March 2016
Meena Mahajan, Nitin Saurabh

Some Complete and Intermediate Polynomials in Algebraic Complexity Theory

Revisions: 2

We provide a list of new natural VNP-intermediate polynomial
families, based on basic (combinatorial) NP-complete problems that
are complete under \emph{parsimonious} reductions. Over finite
fields, these families are in VNP, and under the plausible
hypothesis $\text{Mod}_pP \not\subseteq P/\text{poly}$, are neither VNP-hard (even under
oracle-circuit reductions) nor in VP. Prior to ... more >>>


TR17-153 | 9th October 2017
Pranjal Dutta, Nitin Saxena, Amit Sinhababu

Discovering the roots: Uniform closure results for algebraic classes under factoring

Newton iteration (NI) is an almost 350 years old recursive formula that approximates a simple root of a polynomial quite rapidly. We generalize it to a matrix recurrence (allRootsNI) that approximates all the roots simultaneously. In this form, the process yields a better circuit complexity in the case when the ... more >>>


TR18-124 | 6th July 2018
Amir Yehudayoff

Separating Monotone VP and VNP

This work is about the monotone versions of the algebraic complexity classes VP and VNP. The main result is that monotone VNP is strictly stronger than monotone VP.

more >>>



ISSN 1433-8092 | Imprint