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

DOI10.1007/978-3-030-79416-3_5MaRDI QIDQ2117077zbMATH OpenOpenAlexFDO

Authors 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

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

Cited in

(2)

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

Describes a project that uses

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)