Semidefinite programming and arithmetic circuit evaluation
From MaRDI portal
Publication:943844
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
Related Items
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
