Loading...
Loading...

Go to the content (press return)

Definable ellipsoid method, sums-of-squares proofs, and the isomorphism problem

Author
Atserias, A.; Ochremiak, J.
Type of activity
Presentation of work at congresses
Name of edition
33rd Annual ACM/IEEE Symposium on Logic in Computer Science
Date of publication
2018
Presentation's date
2018-07-12
Book of congress proceedings
Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science
First page
66
Last page
75
Publisher
Association for Computing Machinery (ACM)
DOI
10.1145/3209108.3209186
Project funding
A unified theory of algorithmic relaxations
TASSAT3: Teoría y Aplicaciones en Satisfactibilidad y Optimización de Restricciones
Repository
http://hdl.handle.net/2117/129966 Open in new window
URL
https://dl.acm.org/citation.cfm?id=3209186 Open in new window
Abstract
The ellipsoid method is an algorithm that solves the (weak) feasibility and linear optimization problems for convex sets by making oracle calls to their (weak) separation problem. We observe that the previously known method for showing that this reduction can be done in fixed-point logic with counting (FPC) for linear and semidefinite programs applies to any family of explicitly bounded convex sets. We use this observation to show that the exact feasibility problem for semidefinite programs is e...
Citation
Atserias, A.; Ochremiak, J. Definable ellipsoid method, sums-of-squares proofs, and the isomorphism problem. A: Annual ACM/IEEE Symposium on Logic in Computer Science. "Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science". New York: Association for Computing Machinery (ACM), 2018, p. 66-75.
Keywords
Computer circuits, Ellipsoid method, Fixed-point logic, Graph isomorphism problem, Linear programming, Semidefinite programming, Set theory, Sums-of-squares
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods

Participants

  • Atserias, Albert  (author and speaker )
  • Ochremiak, Joanna  (author and speaker )

Attachments