On the Bit Complexity of Sum-of-Squares Proofs

Naum Z Shor, Class of global minimum bounds of polynomial functions , Cybernetics 23

1987

Earlier work this paper cites.

William Adams and Philippe Loustaunau, An introduction to gröbner bases , American Mathematical Society, 1994

1994

Earlier work this paper cites.

Jean Bernard Lasserre, Optimisation globale et théorie des moments , Comptes Rendus de l’Académie des Sciences-Series I-Mathematics 331

2000

Earlier work this paper cites.

Yurii Nesterov, Squared functional systems and optimization problems , High performance optimization, Springer, 2000, pp. 405–440

2000

Earlier work this paper cites.

Pablo A Parrilo, Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization , Ph.D. thesis, California Institute of Technology, 2000

2000

Earlier work this paper cites.

Gerald B. Folland, How to integrate a polynomial over a sphere , The American Mathematical Monthly 108

2001

Earlier work this paper cites.

D. Grigoriev, Complexity of positivstellensatz proofs for the knapsack , computational complexity 10

2001

Cited alongside, same era.

Dima Grigoriev and Nicolai Vorobjov, Complexity of null-and positivstellensatz proofs , Annals of Pure and Applied Logic 113

2001

Cited alongside, same era.

Jean B Lasserre, Global optimization with polynomials and the problem of moments , SIAM Journal on Optimization 11

2001

Cited alongside, same era.

Monique Laurent, Sums of squares, moment matrices and optimization over polynomials , Emerging applications of algebraic geometry, Springer, 2009, pp. 157–270

2009

Cited alongside, same era.

B. Barak, P. Raghavendra, and D. Steurer, Rounding semidefinite programming hierarchies via global correlation , Proc. FOCS, IEEE, 2011, pp. 472–481

2011

Cited alongside, same era.

Venkatesan Guruswami and Ali Kemal Sinop, Lasserre hierarchy, higher eigenvalues, and approximation schemes for graph partitioning and quadratic integer programming with PSD objectives , IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, 2011, pp. 482–491

2011

Later among the works it cites.

Boaz Barak, Fernando G.S.L. Brandao, Aram W. Harrow, Jonathan Kelner, David Steurer, and Yuan Zhou, Hypercontractivity, sum-of-squares proofs, and their applications , Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing (New York, NY, USA), STOC ’12, ACM, 2012, pp. 307–326

2012

Later among the works it cites.

Boaz Barak and David Steurer, Sum-of-squares proofs and the quest toward optimal algorithms , In Proceedings of the 2014 International Congress of Mathematicians. International Mathematical Union (2014)

2014

Later among the works it cites.