Weighted sum-of-squares lower bounds for univariate polynomials imply \(\mathsf{VP} \neq \mathsf{VNP}\)

Sums of squares and representations by other particular quadratic forms (11E25) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Arithmetic circuits: the chasm at depth four gets wider
Interpolation in Valiant's theory
Lower bounds by Birkhoff interpolation
On the order of approximation in approximative triadic decompositions of tensors
Lower bounds for polynomials with algebraic coefficients
Extremal psd forms with few terms
A probabilistic remark on algebraic program testing
Hardness vs randomness
Grundzüge einer arithmetischen Theorie der algebraischen Grössen. (Festschrift zu Herrn Ernst Eduard Kummers fünfzigjährigem Doctor-Jubiläum, 10 September 1881)
Mathematical problems for the next century
On the linear independence of shifted powers
The complexity of factors of multivariate polynomials
On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?
On the complexity of the permanent in various computational models
Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
A quadratic lower bound for homogeneous algebraic branching programs
Improved bounds for reduction to depth 4 and depth 3
Geometric complexity theory. I: An approach to the P vs. NP and related problems
Algebraic Complexity Classes
Geometric complexity theory. V: Efficient algorithms for Noether normalization
Fast Parallel Computation of Polynomials Using Few Processors
Arithmetic Circuits: A survey of recent results and open questions
Lower Bounds for Sums of Powers of Low Degree Univariates
Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties
Fast Probabilistic Algorithms for Verification of Polynomial Identities
Boundaries of VP and VNP
Determinant: Old Algorithms, New Insights
Polynomials with Rational Coefficients Which are Hard to Compute
Bootstrapping variables in algebraic circuits
A PSPACE construction of a hitting set for the closure of small algebraic circuits
Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits
A Sum of Squares Approximation of Nonnegative Polynomials
Non-commutative circuits and the sum-of-squares problem
Über höhere Kongruenzen.
Derandomizing polynomial identity tests means proving circuit lower bounds

This page was built for publication: Weighted sum-of-squares lower bounds for univariate polynomials imply \(\mathsf{VP} \neq \mathsf{VNP}\)

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