Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with VBP:
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 >>>

ISSN 1433-8092 | Imprint