April 17, 2014

Horizons in TCS: A Celebration of Mihalis Yannakakis’s 60th Birthday — August 27-29, 2013

 

ADDED: Some photos, AND slides from the workshop.  Slides are linked to from the talk schedule below.

A big Thanks to everyone who made this event a success!
 
 
Description:  Professor Mihalis Yannakakis has been one of the leading lights in theoretical computer science for many years, and he has made deep and lasting contributions to an extraordinary range of topics in theory, including in algorithms and complexity theory, combinatorial optimization, automated verification and testing theory, and database theory. This workshop will bring together leading researchers in diverse areas of theoretical computer science in order to celebrate Yannakakis's 60th birthday, and to survey the state of the art and future horizons in the various subfields of theoretical computer science that have been strongly influenced by Yannakakis's work.
 
Biography: Mihalis Yannakakis is currently the Hudson Professor of Computer Science at Columbia University.  He received his Ph.D. in computer science from Princeton University in 1979, and he then spent many years at Bell Laboratories, where he headed the Computing Principles Research Department. He was a professor of computer science at Stanford University before joining Columbia University in 2004. Yannakakis is a recipient of the 2005 Knuth Prize, a Fellow of the ACM, and a member of the National Academy of Engineering. 
 
Dates: This workshop will run for three full days, starting August 27th and ending August 29th and it will be located at the Princeton computer science department (Friend Center 101 auditorium).

 

 
 
Program/Schedule:
 

Tuesday August 27 

8:30-9:00 – Continental breakfast (Convocation room 113, Friend Center)

9:00-10:00 – Christos Papadimitriou, "Algorithms, Complexity, and Mihalis"  (PPT)

10:00-11:00 – Vijay Vazirani, "Dichotomies in Equilibrium Computation: Markets Provide a Surprise" (PPT)

11:00-11:30 – coffee break 

11:30-12:30 – Rajeev Alur, "Regular Functions"

12:30-2:00 – Lunch (Convocation room 113, Friend Center)

 

2:00-3:00 – Jeffrey Ullman, "Computation/Communication Tradeoffs for MapReduce"   (PPT, PDF)

3:00-4:00 – David Johnson, "Open and Closed Problems in NP-Completeness"

4:00-4:30 – coffee break

4:30-5:30 – Gerard Holzmann, "Proof or Consequences"

5:30-6:30 – drinks reception (Convocation room 113, Friend Center)

 

Wednesday August 28

8:30-9:00 – Continental breakfast (Convocation room 113, Friend Center)

9:00-10:00 – Uriel Feige, "Exploring the Border between P and NP" (PPT)

10:00-11:00 – Ronald de Wolf, "Exponential Lower Bounds for Polytopes in Combinatorial Optimization" (PDF)

11:00-11:30 – coffee break

11:30-12:30 – Moshe Vardi, "The Rise and Fall of Linear Temporal Logic" (PDF)

12:30-2:00 – Lunch (Convocation room 113, Friend Center)

 

2:00-3:00 – Phokion Kolaitis, "Aspects of Database Query Evaluation" (PDF)

3:00-4:00 – Lisa Zhang, "Multi-Carrier Multi-Rate Utility Optimization in Heterogeneous Networks via CSMA-Based Algorithms"

4:00-4:30 – coffee break

4:30-5:30 – Kousha Etessami, "Probability, Recursion, Games, and Fixed Points" (PDF)

 

Thursday August 29 

8:30-9:00 – Continental breakfast (Convocation room 113, Friend Center)

9:00-10:00 – Sanjeev Arora, "Is Intractability a Barrier in Machine Learning?"
 

10:00-11:00 – Eva Tardos, "Games, Auctions, Learning, and the Price of Anarchy"

11:00-11:30 – coffee break 

11:30-12:30 – David Lee, "Memory Efficient Routing Table Design and Fast IP Lookup for High-end Core Routers"

12:30-2:00 – Lunch (Convocation room 113, Friend Center)

 

2:00-3:00 – Ilias Diakonikolas, "Approximation in Multiobjective Optimization"  (PDF)

3:00-4:00 – Final Remarks (Mihalis)

 

Directions: We are located next to the Friend Center. A university map of the building location is available here.
 
Organizers: 
Rajeev Alur (UPenn)
Kousha Etessami (Edinburgh)
Christos Papadimitriou (Berkeley)
Moshe Vardi (Rice)
Vijay Vazirani (Georgia Tech)
Avi Wigderson (IAS)
 
Speakers: 
Rajeev Alur (UPenn)
Sanjeev Arora (Princeton)
Ilias Diakonikolas (Edinburgh)
Kousha Etessami (Edinburgh)
Uriel Feige (Weizmann)  
Gerard Holzmann (JPL)
David Johnson (ATT Research)
Phokion Kolaitis (IBM Research)
David Lee (HP Labs)
Christos Papadimitriou (Berkeley)
Eva Tardos (Cornell)
Jeffrey Ullman (Stanford)
Moshe Vardi (Rice)
Vijay Vazirani (Georgia Tech)
Ronald de Wolf (CWI-Amsterdam)
Lisa Zhang (Bell Labs)
Mihalis Yannakakis (Columbia University)

 

 

Hotel: If you plan to come to the workshop and need a hotel room, we suggest that you reserve a room at the Nassau Inn as soon as possible. Their phone number is 1-800-862-7728. Please use workshop Booking ID 17888  – such a rate will only be available if you book over the phone and not online! The cutoff date is Wednesday July 31, 2013.

Early and Late check-in charges will be applied if the hotel is not notified in advance of your need to do so.

 

 

 

Information for Speakers: We are covering the travel costs for all speakers. Speakers getting travel support are expected to use US flag carriers (NSF policy), but in exceptional cases we do have some unrestricted funds that can be used to pay for flights on non-US carriers. Once the workshop is over, you will have 30 days to submit your expense report as described here.
 
Important: If the travel includes stops in addition to the workshop location, appropriate documentation including the fare comparison direct to/from the conference location at the time of purchase must be included with the request for reimbursement. Documentation/comparisons cannot be dated after the trip dates. Question regarding fare comparisons can be directed to Mitra Kelly (mkelly).
 
Parking/Shuttles: There is visitor parking available in Lot 21, but is limited due to construction. Please carpool and arrive early.  Shuttle service from this lot will bring you to the CS bldg; use the East commuter line but note that it will run on a modified schedule in August which is available here. There are also metered spots in front of the dept. but limited in number and take only coins. Parking is not allowed in Campus garages or employee lots.   Update: Lot 23 is also available (further away; it is serviced by shuttle, but some walking will be necessary).   For details of Princeton U. shuttle services, see here.  An interactive map of parking lots and campus buildings is available, see here.
 
 
Directions: The hotel will be the Nassau Inn.  A map of the general area is available here. There is a shuttle service you can reserve in advance called State Shuttle Airporter-formerly the Olympic Shuttle (ask for PU rate). A list of Princeton Taxis is available here. The Newark airport website should also have information regarding transportation. You can also click here for information for Princeton university visitors including driving directions and maps.
 
Registration: Registration is mandatory due to limited seating. ONLINE REGISTRATION HAS CLOSED. However, it will still be possible to register on-site at the workshop (there is still no registration fee).