Session 1: Quantum weak coin-flipping with bias of 0.192 Carlos Mochon Quantum and classical strong direct product theorems and optimal time-space tradeoffs Hartmut Klauck and Robert Spalek and Ronald de Wolf Quantum walk algorithm for element distinctness Andris Ambainis Quantiziation of Classical Walk Based Algorithms Mario Szegedy Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation Dorit Aharonov and Wim van Dam and Julia Kempe and Zeph Landau and Seth Lloyd and Oded Regev Session 2: Maximizing quadratic programs: extending Grothendieck's inequality Moses Charikar and Anthony Wirth An approximate max-Steiner-tree-packing min-Steiner-cut theorem Lap Chi Lau Edge-Disjoint Paths in Undirected Planar Graphs Chandra Chekuri and Sanjeev Khanna and F. Bruce Shepherd Machine Minimization for Scheduling Jobs with Interval Constraints Julia Chuzhoy and Sudipto Guha and Sanjeev Khanna and Joseph (Seffi) Naor Session 3: RANDOM EDGE can be exponential on abstract cubes Jiri Matousek and Tibor Szabo On the Integrality Ratio for Asymmetric TSP Moses Charikar and Michel X. Goemans and Howard Karloff The Hardness of Metric Labeling Julia Chuzhoy and Joseph (Seffi) Naor Hardness of buy-at-bulk network design Matthew Andrews Session 4: Hardness of Approximating the Shortest Vector Problem in Lattices Subhash Khot Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique Subhash Khot Optimal Inapproximability Results for MAX-CUT and Other 2-variable CSPs? Subhash Khot and Guy Kindler and Elchanan Mossel and Ryan O'Donnell Assignment-Testers: Towards a Combinatorial Proof of the PCP-Theorem Irit Dinur and Omer Reingold Session 5: Cryptography in NC0 Benny Applebaum and Yuval Ishai and Eyal Kushilevitz An Unconditional Study of Computational Zero Knowledge Salil Vadhan Universally composable protocols with relaxed set-up assumptions Boaz Barak and Ran Canetti and Jesper Buus Nielsen and Rafael Pass On the (Im)possibility of Cryptography with Imperfect Randomness Yevgeniy Dodis and Shien Jin Ong and Manoj Prabhakaran and Amit Sahai Session 6: Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity Brian C. Dean and Michel X. Goemans and Jan Vondrak An edge in time saves nine: LP rounding approximation algorithms Anupam Gupta and R. Ravi and Amitabh Sinha Stochastic Optimization is (almost) as easy as Deterministic Optimization David Shmoys and Chaitanya Swamy $O(\sqrt{\log n})$ approximation to SPARSEST CUT can be found in quadratic time Sanjeev Arora and Elad Hazan and Satyen Kale Maximum Matchings via Gaussian Elimination Marcin Mucha and Piotr Sankowski Session 7: Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game Rahul Savani and Bernhard von Stengel Edge pricing of multicommodity networks for heterogeneous George Karakostas and Stavros G. Kolliopoulos AND Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games Lisa Fleischer and Kamal Jain and Mohammad Mahdian A Polynomial Time Algorithm for Computing the Arrow-Debreu Market Equilibrium for Linear Utilities Kamal Jain The Price of Stability for Network Design with Fair Cost Allocation Elliot Anshelevich and Anirban Dasgupta and Jon Kleinberg and Eva Tardos and Tom Wexler and Tim Roughgarden Session 8: Holographic Algorithms Leslie G. Valiant Hierarchy Theorems for Probabilistic Polynomial Time Lance Fortnow and Rahul Santhanam Private codes or Succinct random codes that are (almost) perfect. Michael Langberg On the List and Bounded Distance Decodibility of the Reed-Solomon Codes Qi Cheng and Daqing Wan Session 9: Multilinear-$NC_1$ $\neq$ Multilinear-$NC_2$ Ran Raz Algebras with Polynomial Identities and Computing the Determinant Steve Chien and Alistair Sinclair Lattice problems in NP intersect coNP Dorit Aharonov and Oded Regev Worst-case to Average-case Reductions based on Gaussian Measures Daniele Micciancio and Oded Regev Session 10: Extracting Randomness from Few Independent Sources Boaz Barak and Russell Impagliazzo and Avi Wigderson Deterministic extractors for bit-fixing sources by obtaining an Ariel Gabizon and Ran Raz and Ronen Shaltiel Constructing Expander Graphs by 2-lifts and Discrepancy vs. Spectral Gap Yonatan Bilu and Nathan Linial Testing Polynomials over General Fields=20 Tali Kaufman and Dana Ron AND Testing Low-Degree Polynomials over Prime Fields Charanjit S. Jutla and Anindya C. Patthak and Atri Rudra and David Zuckerman Session 11: Measured descent: A new embedding method for finite metrics R. Krauthgamer and J. R. Lee and M. Mendel and A. Naor Triangulation and Embedding using Small Sets of Beacons Jon Kleinberg and Alex Slivkins and Tom Wexler A Simple linear time (1+$\varepsilon$)-approximation algorithm for k-means clustering in any dimensions Amit Kumar and Yogish Sabharwal and Sandeep Sen On the Power of Discrete and of Lexicographic Helly-Type Theorems Nir Halman An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching Amit Chakrabarti and Oded Regev Session 12: Dynamic Optimality--Almost Erik D. Demaine and Dion Harmon and John Iacono and Mihai Patrascu No Sorting? Better Searching! Gianni Franceschini and Roberto Grossi Dynamic approximate all-pairs shortest paths in undirected graphs Liam Roditty and Uri Zwick Dynamic Transitive Closure via Dynamic Matrix Inverse Piotr Sankowski Session 13: Dynamic Speed Scaling to Manage Energy and Temperature Nikhil Bansal, Tracy Kimbrel and Kirk Pruhs Optimal Power-Down Strategies John Augustine and Sandy Irani and Chaitanya Swamy On the Streaming Model Augmented with a Sorting Primitive Gagan Aggarwal and Mayur Datar and Sridhar Rajagopalan and Matthias Ruhl Approximating Edit Distance Efficiently Ziv Bar-Yossef and T.S. Jayram and Robert Krauthgamer and Ravi Kumar Session 14: Strong Spatial Mixing for Lattice Graphs with Fewer Colours Leslie Ann Goldberg and Russell Martin and Mike Paterson Shuffling by semi-random transpositions Elchanan Mossel and Yuval Peres and Alistair Sinclair Randomly coloring constant degree graphs Martin Dyer and Alan Frieze and Thomas Hayes and Eric Vigoda. The Exact Satisfiability Threshold for a Potentially Intractible Random Constraint Satisfaction Problem Harold Connamacher and Michael Molloy Session 15: Spectral Analysis of Random Graphs with Skewed Degree Distributions Anirban Dasgupta and John E. Hopcroft and Frank McSherry Learning with Errors in Answers to Membership Queries Laurence Bisht, Nader H. Bshouty and Lawrance Khoury Learnability and Automatizability Misha Alekhnovich and Mark Braverman and Vitaly Feldman and Adam Klivans and Toni Pitassi