Iannis Tourlakis

Comput. Complex., 2011

2010

Integrality Gaps of 2-o(1) for Vertex Cover SDPs in the Lov[a-acute]sz--Schrijver Hierarchy.

[BibT_eX]

[DOI]

Toniann Pitassi

SIAM J. Comput., 2010

2009

On the Tightening of the Standard SDP for Vertex Cover with $ell_1$ Inequalities.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

2008

Vertex Cover Resists SDPs Tightened by Local Hypermetric Inequalities.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2008

2007

Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy.

[BibT_eX]

[DOI]

Toniann Pitassi

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

2006

Proving Integrality Gaps without Knowing the Linear Program.

[BibT_eX]

[DOI]

Theory Comput., 2006

Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy.

[BibT_eX]

[DOI]

Toniann Pitassi

Electron. Colloquium Comput. Complex., 2006

New Lower Bounds for Vertex Cover in the Lovasz-Schrijver Hierarchy.

[BibT_eX]

[DOI]

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005

Towards Optimal Integrality Gaps for Hypergraph Vertex Cover in the Lovász-Schrijver Hierarchy.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2005

2001

Time-Space Tradeoffs for SAT on Nonuniform Machines.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2001

2000

Time-Space Lower Bounds for SAT on Uniform and Non-Uniform Machines.

[BibT_eX]

[DOI]