Non-commutative circuits and the sum-of-squares problem
From MaRDI portal
Publication:5892594
DOI10.1090/S0894-0347-2011-00694-2zbMath1225.03049MaRDI QIDQ5892594
Avi Wigderson, Amir Yehudayoff, Pavel Hrubeš
Publication date: 27 June 2011
Published in: Journal of the American Mathematical Society (Search for Journal in Brave)
lower boundsalgebraic complexityarithmetic complexitysum-of-squares problemmultilinear circuitsnon-commutative polynomialsnon-commutative circuitnon-commutative computations
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)
Related Items
On families of anticommuting matrices ⋮ Unnamed Item ⋮ Barriers for Rank Methods in Arithmetic Complexity ⋮ Gram spectrahedra ⋮ Unnamed Item ⋮ Lower bounds for arithmetic circuits via the Hankel matrix ⋮ Unnamed Item ⋮ Operator scaling: theory and applications ⋮ Hardness magnification near state-of-the-art lower bounds ⋮ Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds and separations for constant depth multilinear circuits
- Boolean function complexity. Advances and frontiers.
- Homogeneous formulas and symmetric polynomials
- Some new results on composition of quadratic forms
- The complexity of partial derivatives
- Compositions of quadratic forms
- A direct version of Shamir and Snir's lower bounds on monotone circuit depth
- Lower bounds on arithmetic circuits via partial derivatives
- Completeness and reduction in algebraic complexity theory
- Zur Darstellung definiter Funktionen als Summe von Quadraten. (To the representation of definite functions as the sum of squares)
- Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- A series of monomial pairings
- A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
- Sums of Squares Formulae With Integer Coefficients
- A Monte-Carlo Algorithm for Estimating the Permanent
- On the Parallel Evaluation of Multivariate Polynomials
- ON YUZVINSKY'S MONOMIAL PAIRINGS
- Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
- An Asymptotic Bound on the Composition Number of Integer Sums of Squares Formulas
- Algebras with Polynomial Identities and Computing the Determinant
- On the number of multiplications necessary to compute certain functions
- On the immersion problem for real projective spaces
- ON THE PRODUCT OF TWO SUMS OF 16 SQUARES AS A SUM OF SQUARES OF INTEGRAL BILINEAR FORMS
- On the hardness of the noncommutative determinant
- Clifford algebras and approximating the permanent
- Multi-linear formulas for permanent and determinant are of super-polynomial size
