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

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

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)

Related Items (1)

Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring

Uses Software

• lowerbounds-survey

Cites Work

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

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