CWI Scientific Meeting
This is the first announcement of the next CWI Scientific Meeting:
Speakers: Steven Pemberton (Distributed and Interactive Systems) and Ronald de Wolf (Algorithms & Complexity)
Time: Friday, January 31, 13.00-14.00
Place: Room Z009 (Euler)
Titles and abstracts are given below.
It is a lunchtime meeting, so sandwiches will be provided before the talks. We hope to see you there!
Tijs van der Storm and Ronald de Wolf
13.00-13.30: Steven Pemberton
Title: Declarative Web Applications
13.30-14.00: Ronald de Wolf
Title: Can linear programs solve NP-hard problems?
Linear programs optimize a linear function of real variables, subject to some linear constraints on those variables. They have been widely used in practice as well as theory, ever since the invention of the simplex method by Kantorovich and Dantzig for use in World War II work, and the polynomial-time algorithms of Khachiyan and Karmarkar from around 1980. In the mid-1980s some people tried to solve NP-hard optimization problems such as Traveling Salesman and Max-Cut by writing them as efficient linear programs. This is unlikely to succeed since it would imply P=NP, but quite hard to disprove. In 1988 Yannakakis showed that using only *symmetric* linear programs, their approach could not succeed. In this talk we show that their approach cannot work in general: linear programs for Traveling Salesman and several other NP-hard problems require an exponential number of linear constraints.
This result is joint work with Samuel Fiorini, Serge Massar, Sebastian Pokutta, and Hans Raj Tiwary (STOC'12, journal version to appear in J. ACM).