------------------------------------------ SUNDAY, May 21 ------------------------------------------ Session 1A 8:35-9:45 Chair: Madhu Sudan Explicit Capacity-Achieving List-Decodable Codes Venkatesan Guruswami and Atri Rudra Gowers Uniformity, Influence of Variables, and PCPs Alex Samorodnitsky and Luca Trevisan Sub-Constant Error Low Degree Test of Almost-Linear Size Dana Moshkovitz and Ran Raz Session 1B 8:35-9:45 Chair: Amin Saberi The Santa Claus Problem Nikhil Bansal and Maxim Sviridenko On maximizing welfare when utility functions are subadditive Uriel Feige A Randomized Polynomial-Time Simplex Algorithm for Linear Programming Jonathan A. Kelner and Daniel A. Spielman ------------------------------------------ Session 2A 10:10-11:20 Chair: Jon Kleinberg Reducibility Among Equilibrium Problems Paul W. Goldberg and Christos H. Papadimitriou The Complexity of Computing a Nash Equilibrium Constantinos Daskalakis and Paul W. Goldberg and Christos H. Papadimitriou The Effect of Collusion in Congestion Games Ara Hayrapetyan and Eva Tardos and Tom Wexler Session 2B 10:10-11:20 Chair: Tal Malkin Black-Box Constructions of Secure Protocols Yuval Ishai and Eyal Kushilevitz and Yehuda Lindell and Erez Petrank Information-Theoretically Secure Protocols and Security under Composition Eyal Kushilevitz and Yehuda Lindell and Tal Rabin Private Approximation of Search Problems Amos Beimel and Paz Carmi and Kobbi Nissim and Enav Weinreb ------------------------------------------ Session 3 11:30-12:30 Chair: Jon Kleinberg Invited Talk: The Changing Face of Web Search: Algorithms, Auctions and Advertising Prabhakar Raghavan ------------------------------------------ Lunch 12:30-2:00 ------------------------------------------ Session 4A 2:00-3:35 Chair: Assaf Naor On the Solution-Space Geometry of Random Constraint Satisfaction Problems Dimitris Achlioptas and Federico Ricci-Tersenghi Counting independent sets up to the tree threshold Dror Weitz The DLT Priority Sampling is Essentially Optimal Mario Szegedy Optimal Phylogenetic Reconstruction Constantinos Daskalakis and Elchanan Mossel and Sebastien Roch Session 4B 2:00-3:35 Chair: Tal Malkin Time-Space Tradeoffs for Implementations of Snapshots Panagiota Fatourou and Faith Ellen Fich and Eric Ruppert Byzantine Agreement in the Full-Information Model in O(log n) rounds Michael Ben-Or and Elan Pavlov and Vinod Vaikuntanathan Fast Leader-Election Protocols with Bounded Cheaters' Edge Spyridon Antonakopoulos Pricing for Fairness: Distributed Resource Allocation for Multiple Objectives Sung-woo Cho and Ashish Goel ------------------------------------------ Session 5A 4:05-4:50 Chair: Assaf Naor Near-Optimal Algorithms for Unique Games Moses Charikar and Konstantin Makarychev and Yury Makarychev New Approximation Guarantee for Chromatic Number Sanjeev Arora and Eden Chlamtac and Moses Charikar Session 5B 4:05-4:50 Chair: Sudipto Guha Finding a Maximum Weight Triangle in Sub-Cubic Time, With Applications Virginia Vassilevska and Ryan Williams Time-Space Trade-Offs for Predecessor Search Mihai Patrascu and Mikkel Thorup ------------------------------------------ Session 6 5:00-5:40 (Best paper award) Chair: Madhu Sudan The PCP Theorem via Gap Amplification Irit Dinur ------------------------------------------ MONDAY, May 22 ------------------------------------------ Session 7A 8:35-9:45 Chair: Frank McSherry A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity Noga Alon and Eldar Fischer and Ilan Newman and Asaf Shapira Graph limits and parameter testing Christian Borgs and Jennifer T. Chayes and Laszlo Lovasz and Vera T. Sos and Balazs Szegedy and Katalin Vesztergombi Advances in Metric Embedding Theory Ittai Abraham, Yair Bartal and Ofer Neiman Session 7B 8:35-9:45 Chair: Tal Malkin Zero Knowledge with Efficient Provers Minh-Huyen Nguyen and Salil Vadhan Zero-knowledge against quantum attacks John Watrous Local Zero Knowledge Silvio Micali and Rafael Pass ------------------------------------------ Session 8A 10:10-11:20 Chair: Piotr Indyk A Quasi-Polynomial Time Approximation Scheme for Minimum Weight Triangulation Jan Remy and Angelika Steger Building triangulations with epsilon-nets Kenneth L. Clarkson The distance trisector curve Tetsuo Asano and Jiri Matousek and Takeshi Tokuyama Session 8B 10:10-11:20 Chair: Madhu Sudan Conditional Hardness for Approximate Coloring Irit Dinur, Elchanan Mossel, Oded Regev Clique-width minimization is NP-hard Michael R. Fellows and Frances A. Rosamond and Udi Rotics and Stefan Szeider Hardness of Approximate Two-level Logic Minimization and PAC Learning with Membership Queries Vitaly Feldman ------------------------------------------ Session 9 11:30-12:30 (Invited talk) Chair: Allan Borodin Invited Talk: Can Every Randomized Algorithm be Derandomized? Russell Impagliazzo ------------------------------------------ Lunch 12:30-2:00 ------------------------------------------ Session 10A 2:00-3:35 Chair: Sudipto Guha Finding small balanced separators Uriel Feige and Mohammad Mahdian Graph Partitioning using Single Commodity Flows Rohit Khandekar and Satish Rao and Umesh Vazirani Linear time low tree-width partitions and algorithmic consequences Jaroslav Nesetril and Patrice Ossona de Mendez Approximating chromatic number and list-chromatic number in minor-closed and odd-minor-closed classes of graphs Ken-ichi Kawarabayashi and Bojan Mohar Session 10B 2:00-3:35 Chair: Scott Aaronson Hyperbolic Polynomials Approach to Van der Waerden/Schrijver-Valiant like Conjectures Leonid Gurvits A Polynomial Quantum Algorithm for Approximating the Jones Polynomial Dorit Aharonov and Vaughan Jones and Zeph Landau On the Fourier tails of bounded functions over the discrete cube Irit Dinur and Ehud Friedgut and Guy Kindler and Ryan O'Donnell Lattice Problems and Norm Embeddings Oded Regev and Ricky Rosen ------------------------------------------ Session 11A 4:05-4:50 Chair: Dieter van Melkebeek Pseudorandom Walks on Regular Digraphs and the RL vs. L Problem Omer Reingold, Luca Trevisan and Salil Vadhan An efficient algorithm for solving word equations Wojciech Plandowski Session 11B 4:05-4:50 Chair: Amin Saberi Online Trading Algorithms and Robust Option Pricing Peter DeMarzo and Ilan Kremer and Yishay Mansour On Adequate Performance Measures for Paging Konstantinos Panagiotou and Alexander Souza ------------------------------------------ Session 12 5:00-5:50 (Co-winners of Lewin best student paper award) Chair: Dieter van Melkebeek Extractors for a Constant Number of Polynomial Min-Entropy Independent Sources Anup Rao Narrow Proofs May Be Spacious: Separating Space and Width in Resolution Jakob Nordstrom ------------------------------------------ TUESDAY, May 23 ------------------------------------------ Session 13A 8:55-10:30 Chair: Frank McSherry Logarithmic Hardness of the Directed Congestion Minimization Problem Matthew Andrews and Lisa Zhang Hardness of Cut Problems in Directed Graphs Julia Chuzhoy and Sanjeev Khanna Integrality Gaps for Sparsest Cut and Minimum Linear Arrangement Problems Nikhil Devanur and Subhash Khot and Rishi Saket and Nisheeth Vishnoi On Earthmover Distance, Metric Labeling, and 0-Extension Howard Karloff and Subhash Khot and Aranyak Mehta and Yuval Rabani Session 13B 8:55-10:30 Chair: Piotr Indyk Approximate Nearest Neighbors and the Fast Johnson-Lindenstrauss Transform Nir Ailon and Bernard Chazelle On the Importance of Idempotence Sunil Arya and Theocharis Malamatos and David Mount Searching Dynamic Point Sets in Spaces with Bounded Doubling Dimension. Richard Cole and Lee-Ad Gottlieb Learning a Circuit by Injecting Values Dana Angluin and James Aspnes and Jiang Chen and Yinghua Wu ------------------------------------------ Session 14A 10:55-12:30 Chair: Scott Aaronson Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf Limitations of Quantum Coset States for Graph Isomorphism Sean Hallgren, Cristopher Moore, Martin Roetteler, Alexander Russell, and Pranab Sen. A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs Andris Ambainis, Robert Spalek and Ronald de Wolf New upper and lower bounds for randomized and quantum Local Search Shengyu Zhang Session 14B 10:55-12:30 Chair: Allan Borodin New Trade-Offs in Cost-Sharing Mechanisms Tim Roughgarden and Mukund Sundararajan Simple Cost-sharing Schemes for Multi-Commodity Rent-or-Buy and Stochastic Steiner Tree Lisa Fleischer and Jochen Koenemann and Stefano Leonardi and Guido Schaefer Truthful Randomized Mechanisms for Combinatorial Auctions Shahar Dobzinski and Noam Nisan and Michael Schapira Fast Convergence to Wardrop Equilibria by Adaptive Sampling Methods Simon Fischer and Harald Racke and Berthold Vocking ------------------------------------------ Lunch 12:30-2:00 ------------------------------------------ Session 15A 2:00-4:00 Chair: Scott Aaronson 2-Source Dispersers for n^o(1) Entropy, and Ramsey Graphs Beating the Frankl-Wilson Construction Boaz Barak and Anup Rao and Ronen Shaltiel and Avi Wigderson Linear Degree Extractors and the Inapproximability of Max-Clique and Chromatic Number David Zuckerman Deterministic Extractors For Small Space Sources Jesse Kamp and Anup Rao and Salil Vadhan and David Zuckerman On Basing One-Way Functions on NP-Hardness Adi Akavia and Oded Goldreich and Shafi Goldwasser and Dana Moshkovitz On the Randomness Complexity of Efficient Sampling Bella Dubrov and Yuval Ishai Session 15B 2:00-4:00 Chair: Jon Kleinberg A Quasi-PTAS for Unsplittable Flow on Line Graphs Nikhil Bansal and Amit Chakrabarti and Amir Epstein and Baruch Schieber Minimizing Average Flow Time on Related Machines Naveen Garg and Amit Kumar Provably Near-Optimal Sampling-Based Algorithms for Stochastic Inventory Models Retsef Levi and Robin Roundy and David Shmoys A subset spanner for planar graphs,with application to subset TSP Philip N. Klein Edge-Disjoint Paths in Planar Graphs with Constant Congestion C. Chekuri and S. Khanna and F.B. Shepherd