DOS Seminar - Arefin Hug

Event Details
  • Date/Time:
    • Wednesday April 22, 2015
      12:00 pm
  • Location: Executive Education Room 228 Main
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact
No contact information submitted.
Summaries

Summary Sentence: DOS Seminar - Arefin Hug

Full Summary: No summary paragraph submitted.

TITLE: The matching problem has no small symmetric SDP

ABSTRACT:

Yannakakis showed that the matching problem does not have a small symmetric linear program. RothvoƟ recently proved that any (not necessarily symmetric) linear program also has exponential size. It is natural to ask whether the matching problem can be expressed compactly in a framework such as semidefinite programming (SDP) that is more powerful than linear programming but still allows efficient optimization. We answer this question negatively for symmetric SDPs: any symmetric SDP for the matching problem has exponential size. We also show that an O(k)-round Lasserre SDP relaxation for the metric traveling salesperson problem (TSP) yields at least as good an approximation as any symmetric SDP relaxation of size n^k. The key technical ingredient underlying both these results is an upper bound on the degree needed to derive polynomial identities that hold over the space of matchings or traveling salesperson tours.

This is joint work with Jonah Brown-Cohen, Prasad Raghavendra and Benjamin Weitz from Berkeley, and Gabor Braun, Sebastian Pokutta, Aurko Roy and Daniel Zink at Georgia Tech.

Speaker Bio:

Arefin Huq is a PhD student in the Theory group of the College of Computing at Georgia Tech, currently focusing on the connection between computational complexity and combinatorial optimization. He has previously done work on Kolmogorov complexity, machine learning, and automated emotion recognition in music.




Additional Information

In Campus Calendar
No
Groups

School of Industrial and Systems Engineering (ISYE)

Invited Audience
Undergraduate students, Faculty/Staff, Graduate students
Categories
Seminar/Lecture/Colloquium
Keywords
No keywords were submitted.
Status
  • Created By: Anita Race
  • Workflow Status: Published
  • Created On: Apr 20, 2015 - 4:01am
  • Last Updated: Apr 13, 2017 - 5:19pm