Larry Stockmeyer Commemoration: =============================== Saturday, May 21, 2005 9:15 - 10:45 Nicholas Pippenger Larry Stockmeyer's Work in Computational Complexity Theory 10:45 - 11:15 BREAK 11:15 - 11:55 Albert Meyer What We Were Thinking: A Supervisor's Reminiscence 11:55 - 1:30 LUNCH (on our own) 1:30 - 2:10 Richard Karp Congestion-Delay Trade-Offs in Geographically Distributed Networks 2:10 - 2:50 Anne Condon What can be Proved to a Finite State Verifier? Larry Stockmeyer's Contributions to Interactive Proof Systems 2:50 - 3:30 Miklos Ajtai Secure Computing 3:30 - 4:00 BREAK 4:00 - 4:40 Christopher Umans Optimization Problems in the Polynomial-Time Hierarchy 4:40 - 5:20 Cynthia Dwork Larry Stockmeyer's Last Work et Sequelae 5:20 – 5:30 Remarks STOC 2005 Conference Program: ============================= Saturday, May 21, 2005 6:00 - 9:00 pm : Reception Sunday, May 22 7:30 - 8:30 am : Continental Breakfast 8.30 - 10.10 : Session 1A Chair: Amnon Ta-Shma Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson Extractors with Weak Random Seeds Ran Raz Pseudorandom Generators for Low Degree Polynomials Andrej Bogdanov On Uniform Amplification of Hardness in NP Luca Trevisan 8.30 - 10.10 : Session 1B Chair: Tim Roughgarden Approximation Techniques for Utilitarian Mechanism Design Patrick Briest, Piotr Krysta, Berthold Vöcking Computing Correlated Equilibria in Multi-Player Games Christos H. Papadimitriou The Price of Routing Unsplittable Flow B. Awerbuch, Y. Azar, A. Epstein & The Price of Anarchy of Finite Congestion Games George Christodoulou, Elias Koutsoupias Market Equilibrium via the Excess Demand Function Bruno Codenotti, Benton McCune, Kasturi Varadarajan 10.10 - 10.35 : Coffee Break 10.35 - 11.25 : Session 2A Chair: Jin-Yi Cai On Lattices, Learning with Errors, Random Linear Codes, and Cryptography Oded Regev Representing Hard Lattices with O(n log n) Bits Miklos Ajtai 10.35 - 11.25 : Session 2B Chair: Claire Kenyon On Dynamic Range Reporting in One Dimension Christian Worm Mortensen, Rasmus Pagh, Mihai Patrascu Worst-Case Update Times for Fully-Dynamic All-Pairs Shortest Paths Mikkel Thorup 11.30 - 12.30 pm : Session 3 (Invited talk) Chair: Ronald Fagin Beyond NP: The Work and Legacy of Larry Stockmeyer Lance Fortnow 12:30 - 1:45 : Lunch 1:45 - 3:25 : Session 4A Chair: Ravi Kumar Every Monotone Graph Property is Testable Noga Alon, Asaf Shapira Testing versus Estimation of Graph Properties Eldar Fischer, Ilan Newman Testing Monotone High-Dimensional Distributions Ronitt Rubinfeld, Rocco A. Servedio Efficient Testing of Groups Katalin Friedl, Gabor Ivanyos, Miklos Santha 1:45 - 3:25 : Session 4B Chair: Tim Roughgarden Approximation Algorithms for Network Design with Metric Costs Joseph Cheriyan, Adrian Vetta On Non-uniform Multicommodity Buy-at-Bulk Network Design Moses Charikar, Adriana Karagiozova Multicommodity Flow, Well-linked Terminals, and Routing Problems Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd Oblivious Routing in Directed Graphs with Random Demands MohammadTaghi Hajiaghayi, Jeong Han Kim, Tom Leighton, Harald Räcke 3:25 - 3:45 : Coffee Break 3:45 - 5:25 : Session 5A Chair: Sariel Har-Peled Optimal Approximations of the Frequency Moments of Data Streams Piotr Indyk, David Woodruff Coresets in dynamic Geometric Data Streams Gereon Frahling, Christian Sohler Low Distortion Embeddings for Edit Distance Rafail Ostrovsky, Yuval Rabani Low-distortion Embeddings of General Metrics Into the Line Mihai Badoiu, Julia Chuzhoy, Piotr Indyk, Anastasios Sidiropoulos 3:45 - 5:25 : Session 5B Chair: Ryan O'Donnell Tree-Walking Automata Do Not Recognize All Regular Languages Mikolaj Bojanczyk, Thomas Colcombet Balanced Boolean Functions that can be Evaluated so that Every Input bit is Unlikely to be Read Itai Benjamini, Oded Schramm, David B. Wilson Lower Bounds for $k$-DNF Resolution on Random 3-CNFs Michael Alekhnovich Bounded-depth Circuits: Separating Wires from Gates Michal Koucky, Pavel Pudlak, Denis Therien 8:00 - 10:00 : Business Meeting Monday, May 23 7:30 - 8:30 am : Continental Breakfast 8.30 - 10.10 : Session 6A Chair: Sariel Har-Peled Simple PCPs with Poly-log Rate and Query Complexity Eli Ben-Sasson, Madhu Sudan Hardness of the Undirected Edge-Disjoint Paths Problem Matthew Andrews, Lisa Zhang Hardness of the Undirected Congestion Minimization Problem Matthew Andrews, Lisa Zhang Towards Strong Nonapproximability Results in the Lovasz-Schrijver Hierarchy Mikhail Alekhnovich, Sanjeev Arora, Iannis Tourlakis 8.30 - 10.10 : Session 6B Chair: Jin-Yi Cai Computing the First Betti Number and the Connected Components of Semi-algebraic Sets Saugata Basu, Richard Pollack, Marie-Francoise Roy Polynomial Time Algorithm for Computing the Top Betti Numbers of Semi-algebraic Sets Defined by Quadratic Inequalities Saugata Basu On Algorithms for Discrete and Approximate Brouwer Fixed Points Xi Chen, Xiaotie Deng Convex Programming for Scheduling Unrelated Parallel Machines Y. Azar, A. Epstein 10.10 - 10.35 : Coffee Break 10.35 - 11.25 : Session 7A Chair: Cynthia Dwork The Round Complexity of Two-Party Random Selection Saurabh Sanghvi, Salil Vadhan Hierarchies for Semantic Classes Lance Fortnow, Rahul Santhanam, Luca Trevisan 10.35 - 11.25 : Session 7B Chair: Ravi Kumar Learning with Attribute Costs Haim Kaplan, Eyal Kushilevitz, Yishay Mansour Learning Nonsingular Phylogenies and Hidden Markov Models Elchanan Mossel, Sebastien Roch 11.30 - 12.15 pm : Session 8 (Best paper) Chair: Ronald Fagin Undirected ST-Connectivity in Log-Space Omer Reingold 12:15 - 1:45 : Lunch 1:45 - 3:25 : Session 9A Chair: Anupam Gupta Universal Approximations for TSP, Steiner Tree, and Set Cover Lujun Jia, Guolong Lin, Guevara Noubir, Rajmohan Rajaraman, Ravi Sundaram Saving an Epsilon: A 2-approximation for the k-MST Problem in Graphs Naveen Garg The Mixing Time of the Thorp Shuffle Ben Morris Approximately Counting Integral Flows and Cell-Bounded Contingency Tables Mary Cryan, Martin Dyer, Dana Randall 1:45 - 3:25 : Session 9B Chair: Kamal Jain Spectral Norm of Random Matrices Van Vu On Random +/-1 Matrices: Singularity and Determinant Terence Tao, Van Vu On the Average Case Performance of Some Greedy Approximation Algorithms for the Uncapacitated Facility Location Problem Abraham D. Flaxman, Alan M. Frieze, Juan C. Vera Towards Asymptotic Optimality in Probabilistic Packet Marking Micah Adler, Jeff Edmonds, Jiri Matousek 3:25 - 3:45 : Coffee Break 3:45 - 5:00 : Session 10A Chair: Amnon Ta-Shma Tensor Norms and the Classical Communication Complexity of Nonlocal Quantum Measurement Yaoyun Shi Fast Quantum Algorithms for Computing the Unit Group and Class Group of a Number Field Sean Hallgren & Polynomial Time Quantum Algorithm for the Computation of the Unit Group of a Number Field Arthur Schmidt, Ulrich Vollmer Fast Quantum Byzantine Agreement Michael Ben-Or, Avinatan Hassidim 3:45 - 5:00 : Session 10B Chair: David Karger Quadratic Forms on Graphs Noga Alon, Konstantin Makarychev, Yuri Makarychev, Assaf Naor Lower-Stretch Spanning Trees Michael Elkin, Yuval Emek, Daniel A. Spielman, Shang-Hua Teng Edge Partition of Planar Graphs into two Outerplanar Graphs Daniel Goncalves 5:30 : Buses leave for social event Tuesday, May 24 7:30 - 8:30 am : Continental Breakfast 8.30 - 10.10 : Session 11A Chair: Cynthia Dwork Covert Two-Party Computation Luis von Ahn, Nicholas J. Hopper, John Langford On Obfuscating Point Functions Hoeteck Wee New and Improved Constructions of Non-Malleable Cryptographic Protocols Rafael Pass, Alon Rosen Collusion-Free Protocols Matt Lepinksi, Silvio Micali, abhi shelat 8.30 - 10.10 : Session 11B Chair: Anupam Gupta Euclidean Distortion and the Sparsest Cut Sanjeev Arora, James R. Lee, Assaf Naor Improved Approximation Algorithms for Minimum-Weight Vertex Separators Uriel Feige, MohammadTaghi Hajiaghayi, James R. Lee O(\sqrt{log n}) Approximation Algorithms for Min UnCut, Min 2CNF Deletion, and Directed Cut Problems Amit Agarwal, Moses Charikar, Konstantin Makarychev, Yury Makarychev Balanced Metric Labeling Joseph (Seffi) Naor, Roy Schwartz 10.10 - 10.35 : Coffee Break 10.35 - 11.25 : Session 12A Chair: Russell Impagliazzo Locally Decodable Codes with 2 Queries and Polynomial Identity Testing for Depth 3 Circuits Zeev Dvir, Amir Shpilka Limits to List Decoding Reed-Solomon Codes Venkatesan Guruswami, Atri Rudra 10.35 - 11.25 : Session 12B Chair: Kamal Jain Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders Shahar Dobzinski, Noam Nisan, Michael Schapira Derandomization of Auctions Gagan Aggarwal, Amos Fiat, Andrew Goldberg, Jason Hartline, Nicole Immorlica, Madhu Sudan 11.30 - 12.15 pm : Session 13 (Best student paper) Chair: Tim Roughgarden A O(log n log log n) Space Algorithm for Undirected st-Connectivity Vladimir Trifonov 12:15 - 1:45 : Lunch 1:45 - 3:25 : Session 14A Chair: Russell Impagliazzo The Complexity of Agreement Scott Aaronson Concurrent General Composition of Secure Protocols in the Timing Model Yael Tauman Kalai, Yehuda Lindell, Manoj Prabhakaran Correcting Errors Without Leaking Partial Information Yevgeniy Dodis, Adam Smith Key Agreement from Weak Bit Agreement Thomas Holenstein 1:45 - 3:25 : Session 14B Chair: Adam Tauman Kalai A New Strategy for Querying Priced Information Ferdinando Cicalese, Eduardo Sany Laber Aggregating Inconsistent Information: Ranking and Clustering Nir Ailon, Moses Charikar, Alantha Newman On the Bias of Traceroute Sampling, or, Power-law Degree Distributions in Regular Graphs Dimitris Achlioptas, Aaron Clauset, David Kempe, Cristopher Moore How to Spread Adversarial Nodes? Rotate! Christian Scheideler 3:25 - 3:45 : Coffee Break 3:45 - 5:00 : Session 15A Chair: Ryan O'Donnell From a Static Impossibility to an Adaptive Lower Bound: The Complexity of Early Deciding Set Agreement Eli Gafni, Rachid Guerraoui, Bastian Pochon An Optimal Multi-Writer Snapshot Algorithm Prasad Jayanti Cooperative Asynchronous Update of Shared Memory Bogdan Chlebus, Dariusz Kowalski 3:45 - 5:00 : Session 15B Chair: Claire Kenyon Every 2-CSP Allows Nontrivial Approximation Johan Håstad Tensor Decomposition and Approximation Schemes for Constraint Satisfaction Problems W. Fernandez dela Vega, Ravi Kannan, Marek Karpinski, Santosh Vempala On Strip Packing with Rotations Klaus Jansen, Rob van Stee