"Barriers in Computational Complexity II" workshop
August 26 – 30, 2010
Continuing the program that started with the first Barriers in Computational Complexity workshop in 2009, this workshop will focus on identifying and circumventing barriers that are preventing progress in several sub-fields of Computational Complexity.
This workshop will focus on five sub-fields that were not covered in the 2009 workshop: approximation algorithms and hardness of approximation, quantum computation, cryptography, communication and information in complexity and (geo)metric algorithms.
Here is a list of talks with slides:
Thursday, August 26
Approximation Algorithms and Hardness of Approximation
Organizer: Moses Charikar
Mohit Singh : Iterative Methods in Combinatorial Optimization [slides]
Seffi Naor : Online Algorithms, Linear Programming, and the k-Server Problem [slides]
[Video]
Sanjeev Arora : Semidefinite Programming based Approximation Algorithms [slides]
[Video]
Prasad Raghvendra : Complexity of CSPs: Exact and Approximation [slides]
[Video]
David Steurer : Subexponential Algorithms for Unique Games and Related Problems [slides]
[Video]
Friday August 27
Recent Advances and Challenges in Cryptography
Organizers: Shafi Goldwasser and Yuval Ishai
Daniele Micciancio (UCSD): Solving All Lattice Problems in Deterministic Single ExponentiaTime [slides]
[Video]
Craig Gentry (IBM Research): Directions in Homomorphic Encryption [slides]
[Video]
Omer Reingold (Microsoft Research & Weizmann): The Many Entropies in One-Way Functions [slides]
[Video]
Rafael Pass (Cornell): Concurrency and Parallel Repetition [slides]
[Video]
Vinod Vaikuntanathan (Microsoft Research): New Developments in Leakage-Resilient Cryptography [slides]
[Video]
Guy Rothblum (Princeton & IAS): Differentially Private Data Analysis: Progress and Challenges [slides]
[Video]
Saturday August 28
Quantum computation
Organizers: Scott Aaronson and Umesh Vazirani
Scott Aaronson: The Computational Complexity of Linear Optics [slides]
[Video]
Umesh Vazirani: Challenges of Hamiltonian Complexity [slides]
[Video]
Ronald deWolf: Quantum Proofs for Classical Theorems [slides]
[Video]
Chris Peikert: Lattices and Quantum Computation: Barriers and Opportunities [slides]
[Video]
Sunday August 29
Title: Communication and information in complexity
Organizer: Paul Beame
Paul Beame: Communication Complexity and Applications: An introduction and survey [slides]
T.S. Jayram: Information Complexity and the Geometry of Communication [slides]
Alexander Sherstov: Quantum and Unbounded-Error Communication Complexity [slides]
[Video]
Mihai Patrascu: Lower Bounds for Data Structures [slides]
[Video]
Anup Rao: Direct Sums and Compression in Communication Complexity [slides]
[Video]
Monday August 30
Title: (Geo)metric algorithms
Organizer: Piotr Indyk
Sariel Har-Peled: Finding Haystacks (and Other Structures) in Geometry [slides]
[Video]
Alex Andoni: Nearest neighbor search in high-dimensional spaces [slides]
[Video]
Jeff Erickson: Computational topology: Paths, Cuts, Flows, and Embeddings [slides]
[Video]
Anupam Gupta: Algorithmic applications of doubling metrics [slides]
[Video]
James Lee: Geometric obstructions for the Sparsest Cut problem [slides]
[Video]
Organizing committee:
Michael Saks (chair), Scott Aaronson, Sanjeev Arora, Paul Beame, Moses Charikar, Shafi Goldwasser, Piotr Indyk, Yuval Ishai, Robert Tarjan, Umesh Vazirani
Lodging: If you plan to come to the workshop and need a hotel room, we suggest you register (using the registration form at the bottom of this page) and reserve a room at the Nassau Inn as soon as possible. Their phone number is 1-800-862-7728 or 609-921-7500 and you should ask for group number 14120 or `Barriers workshop' to get the special workshop rate. We encourage you to reserve your room early since the hotel has limited space. DO NOT BOOK YOUR ROOM ONLINE! THE SPECIAL RATE IS ONLY AVAILABLE WHEN MAKING A RESERVATION BY PHONE.
Registration: Please use the form at the bottom of this page to register to the workshop. (Last minute registration is ok but please do not register on the last business day prior to the workshop).
Financial support: We have some limited funds to cover expenses of students attending the workshop. If you need such support please fill in the support request form at the bottom of this page. Once the workshop is over, you will also need to fill the following form: pu-expense-report. Guidelines for filling the expense report are available here. If you are being reimbursed by PU please read the following airfare guidelines carefully. All flights must be booked with a US flagship carrier airlines in order to receive reimbursement for the expense. Ask your travel agent or airline customer service representative if your flight will qualify if in doubt.
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.
While the initial deadline for applications for financial support has past, we will continue to consider applications for support subject to availability of resources.
The Center for Computational Intractability especially encourages the participation in our workshops of researchers from backgrounds that are traditionally underrepresented within the computer science research community.
Local Information
There is a shuttle service you can reserve in advance called Olympic Airporter (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.
Parking for participants is in Lot 21 (see this map) with this pass (place on your dashboard). There is a university shuttle service that connects this parking lot with the workshop location. For timetables click here (look for the West and East Extension Lines summer schedule).
Contact
Questions regarding the scientific program should be directed to barriers.ws2 .
For questions regarding local arrangements contact barriers2.local.
Registration for the workshop is now closed