Semidefinite programming and arithmetic circuit evaluation

DOI10.1016/j.dam.2007.04.023zbMath1163.90694arXivcs/0512035OpenAlexW2123675424MaRDI QIDQ943844

Sergey P. Tarasov, Mikhail N. Vyalyi

Publication date: 10 September 2008

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0512035

zbMATH Keywords

complexitysemidefinite programmingsuccinct representation

Mathematics Subject Classification ID

Semidefinite programming (90C22)

Related Items (5)

SOS Is Not Obviously Automatizable, Even Approximately ⋮ Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem ⋮ Census algorithms for chinese remainder pseudorank ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ Three-monotone interpolation

Cites Work

• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• The complexity of combinatorial problems with succinct input representation
• A polynomial-time algorithm, based on Newton's method, for linear programming
• Geometric algorithms and combinatorial optimization
• On the complexity of semidefinite programs
• An exact duality theory for semidefinite programming and its complexity implications
• Valiant's model and the cost of computing integers
• On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?
• A Mathematical View of Interior-Point Methods in Convex Optimization
• On the Power of Real Turing Machines over Binary Inputs
• Handbook of semidefinite programming. Theory, algorithms, and applications

This page was built for publication: Semidefinite programming and arithmetic circuit evaluation