ARC Colloquium: Gábor Braun

Event Details
  • Date/Time:
    • Monday March 25, 2013
      1:30 pm
  • Location: Klaus 1116W
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact

ndongi@cc.gatech.edu

 

Summaries

Summary Sentence: No summary sentence submitted.

Full Summary: No summary paragraph submitted.

Title: Limiting linear programs through common information

Abstract:

Efficiently optimizing linear functions over a polytope by directly solving the linear program requires a compact representation of the polytope, e.g., as an affine image of a polytope with few facets. We present an information theoretic approach for proving limits of such extension: the common information shared by the vertices and facets.

This framework not only improves recent lower bounds on the CLIQUE polytope by Braverman and Moitra, but also provides a much simplified proof, and is stable under perturbations of the polytope.

This is an ongoing joint work with Sebastian Pokutta.

Additional Information

In Campus Calendar
No
Groups

School of Computer Science, ARC

Invited Audience
No audiences were selected.
Categories
Seminar/Lecture/Colloquium
Keywords
No keywords were submitted.
Status
  • Created By: Elizabeth Ndongi
  • Workflow Status: Published
  • Created On: Feb 27, 2013 - 4:41am
  • Last Updated: Oct 7, 2016 - 10:02pm