Real -conjecture for sum-of-squares: a unified approach to lower bound and derandomization

DOI10.1007/978-3-030-79416-3_5OpenAlexW3177454079MaRDI QIDQ2117077FDOQ2117077

Pranjal Dutta

Publication date: 21 March 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-79416-3_5

zbMATH Keywords

real rootmatrix rigidity\( \tau \)-conjecture\textsf{VNP}\textsf{VP}PIT

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• A probabilistic remark on algebraic program testing
• Hardness vs randomness
• Sums of squares, moment matrices and optimization over polynomials
• Title not available (Why is that?)
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• A Sufficient Condition for All the Roots of a Polynomial To Be Real
• Title not available (Why is that?)
• Mathematical problems for the next century
• A Sum of Squares Approximation of Nonnegative Polynomials
• Communication in bounded depth circuits
• Completeness and reduction in algebraic complexity theory
• A remark on matrix rigidity
• Fast Parallel Computation of Polynomials Using Few Processors
• Arithmetic circuits: the chasm at depth four gets wider
• A note on matrix rigidity
• Arithmetic circuits: a chasm at depth 3
• Arithmetic Circuits: A survey of recent results and open questions
• Superconcentrators
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Extremal psd forms with few terms
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?
• Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
• On defining integers and proving arithmetic circuit lower bounds
• Lower bounds for matrix factorization
• A \(\tau \)-conjecture for Newton polygons
• Title not available (Why is that?)
• Superconcentrators of depths 2 and 3; odd levels help (rarely)
• Title not available (Why is that?)
• Algebraic Complexity Classes
• Title not available (Why is that?)
• Algebraic complexity theory. I: An introduction
• Unifying known lower bounds via geometric complexity theory
• Bootstrapping variables in algebraic circuits
• Static data structure lower bounds imply rigidity
• Geometric complexity theory. V: Efficient algorithms for Noether normalization
• On the distribution of runners on a circle
• Log-Concavity and Lower Bounds for Arithmetic Circuits
• Title not available (Why is that?)
• The real tau‐conjecture is true on average

Cited In (2)

• Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring
• Weighted sum-of-squares lower bounds for univariate polynomials imply \(\mathsf{VP} \neq \mathsf{VNP}\)

Uses Software

• lowerbounds-survey

This page was built for publication: Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization

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