Non-commutative circuits and the sum-of-squares problem

DOI10.1145/1806689.1806781zbMath1293.90045OpenAlexW2020713199MaRDI QIDQ5891429

Amir Yehudayoff, Avi Wigderson, Pavel Hrubeš

Publication date: 13 August 2014

Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1806689.1806781

zbMATH Keywords

lower boundsalgebraic complexity

Mathematics Subject Classification ID

Integer programming (90C10) Sums of squares and representations by other particular quadratic forms (11E25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

On the hardness of the determinant: sum of regular set-multilinear circuits ⋮ Unnamed Item ⋮ Regular expression length via arithmetic formula complexity ⋮ Unnamed Item ⋮ A super-quadratic lower bound for depth four arithmetic circuits

This page was built for publication: Non-commutative circuits and the sum-of-squares problem