Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
type: Item
instance of: scholarly article
title: Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
DOI: 10.1007/978-3-030-79416-3_5
author: Pranjal Dutta
publication date: 2022-03-21T00:00:00Z
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7493525
zbMATH Keywords: \( \tau \)-conjecture
zbMATH Keywords: matrix rigidity
zbMATH Keywords: real root
zbMATH Keywords: \textsf{VP}
zbMATH Keywords: \textsf{VNP}
zbMATH Keywords: PIT
describes a project that uses: lowerbounds-survey
MaRDI profile type: Publication
full work available at URL: 978-3-030-79416-3 5
OpenAlex ID: W3177454079
cites work: Bootstrapping variables in algebraic circuits
cites work: Non-commutative arithmetic circuits: depth reduction and size lower bounds
cites work: Superconcentrators of depths 2 and 3; odd levels help (rarely)
cites work: On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
cites work: The real tau‐conjecture is true on average
cites work: On defining integers and proving arithmetic circuit lower bounds
cites work: Completeness and reduction in algebraic complexity theory
cites work: Algebraic complexity theory. I: An introduction
cites work: A probabilistic remark on algebraic program testing
cites work: Static data structure lower bounds imply rigidity
cites work: A note on matrix rigidity
cites work: Log-Concavity and Lower Bounds for Arithmetic Circuits
cites work: Unifying known lower bounds via geometric complexity theory
cites work: Arithmetic circuits: a chasm at depth 3
cites work: Q3191579
cites work: On the distribution of runners on a circle
cites work: Derandomizing polynomial identity tests means proving circuit lower bounds
cites work: Arithmetic circuits: the chasm at depth four gets wider
cites work: A \(\tau \)-conjecture for Newton polygons
cites work: Lower bounds for matrix factorization
cites work: A Sufficient Condition for All the Roots of a Polynomial To Be Real
cites work: A Sum of Squares Approximation of Nonnegative Polynomials
cites work: Q3601990
cites work: Algebraic Complexity Classes
cites work: Geometric complexity theory. V: Efficient algorithms for Noether normalization
cites work: Hardness vs randomness
cites work: Q4103631
cites work: Superconcentrators
cites work: Communication in bounded depth circuits
cites work: Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
cites work: Q3002820
cites work: Extremal psd forms with few terms
cites work: Fast Probabilistic Algorithms for Verification of Polynomial Identities
cites work: A remark on matrix rigidity
cites work: Arithmetic Circuits: A survey of recent results and open questions
cites work: On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?''
cites work: Mathematical problems for the next century
cites work: Q4138137
cites work: Q4164821
cites work: Fast Parallel Computation of Polynomials Using Few Processors
cites work: Q3851616
description: scientific article; zbMATH DE number 7493525