you're reading...

SACT Seminar: Extension Complexity

Time: 1:30pm Tuesday, 23rd February.

Location: SIT 459

Speaker: David Avis, Kyoto University

Title: Extension Complexity

An overview of extension complexity up to Rothvoss’ result that the matching polytope has exponential extension complexity, then two avenues to move forward. (a) H-free extension complexity which allows certain ‘easy’ constraints to be ignored. (b) An explicit construction of polynomial size polytopes for matching and other problems in P.

(Joint work with D. Bremner, H. Tiwary, and O. Watanabe)



No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 68 other followers

%d bloggers like this: