ARC Colloquium: Friedrich Eisenbrand, EPFL, Lausanne

Event Details
  • Date/Time:
    • Monday October 22, 2012
      1:00 pm
  • Location: Klaus 1116
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact

ndongi@cc.gatech.edu

Summaries

Summary Sentence: Diameter of Polyhedra: Abstractions, new upper bounds and open problems

Full Summary: No summary paragraph submitted.

 

Title: Diameter of Polyhedra: Abstractions, new upper bounds and open problems

Abstract:

One of the most prominent mysteries in convex geometry is the question whether the diameter of a polyhedron is bounded by a polynomial in the number of facets. The gap between the best known lower bound (linear) and the best known upper bound (n^{log d} by Kalai and Kleitman) is impressive.

After Francisco Santos refuted the classical Hirsch conjecture in 2010, the polynomial Hirsch conjecture, stating that the answer to the question above is "Yes", has received considerable attention. In this talk I present the best known bounds mentioned above in a very simple abstract setting that does not involve any geometry. The polynomial Hirsch conjecture is also open in this abstract setting. I furthermore show polynomial upper bounds on the diameter of polyhedra that are defined by matrices with small sub-determinants and close with open problems.

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: Sep 4, 2012 - 4:25am
  • Last Updated: Oct 7, 2016 - 9:59pm