Saturday, 25th Oct.

     Tutorial 1 (Session Chair: Harry Buhrman) 10:00--11:30am
         The Polynomial Method in Quantum and Classical Computing
         Scott Aaronson

     Lunch 11:30am--1:30pm (on your own)

    Tutorial 2 (Session Chair: Mohammad Mahdian) 1:30--3:00pm
         Theory of Sponsored Search Auctions
         Gagan Aggarwal and S. Muthukrishnan

     Break 3:00--3:30pm

     Tutorial 3 (Session Chair: Emanuele Viola) 3:30--5:00pm
         Average-case Complexity
         Luca Trevisan

     Reception 6:00--9:00pm

Sunday 26th Oct.

     Session 1 8:40--10:15am

         Session 1A (Session Chair: Mohammad Mahdian)

         Truthful Approximation Schemes for Single-Parameter Agents
         Peerapong Dhangwatnotai, Shahar Dobzinski, Shaddin Dughmi, and Tim Roughgarden

         Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games
         Constantinos Daskalakis and Christos H. Papadimitriou

         Approximation Algorithms for Single-minded Envy-free Profit-maximization Problems with Limited Supply
         Maurice Cheung and Chaitanya Swamy

         Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents
         Nikhil R. Devanur and Ravi Kannan

                 Session 1B (Session Chair: Emanuele Viola)

                 The Sign-Rank of AC^O
                 Alexander A. Razborov and Alexander A. Sherstov

                 Arithmetic Circuits: A Chasm at Depth Four
                 Manindra Agrawal and V. Vinay

                 Dense Subsets of Pseudorandom Sets
                 Omer Reingold, Luca Trevisan, Madhur Tulsiani, and Salil Vadhan

                 Almost-Natural Proofs
                 Timothy Y. Chow

     Break 10:15--10:45am

     Session 2 10:45am--12:20pm

         Session 2A (Session Chair: Artur Czumaj)

         Dynamic Connectivity: Connecting to Networks and Geometry
         Timothy M. Chan, Mihai Patrascu, and Liam Roditty

         Algorithms for Single-Source Vertex Connectivity
         Julia Chuzhoy and Sanjeev Khanna

         A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
         Glencora Borradaile, Philip N. Klein, and Claire Mathieu

         Degree Bounded Network Design with Metric Costs
         Yuk Hei Chan, Wai Shing Fung, Lap Chi Lau, and Chun Kong Yung

                 Session 2B (Session Chair: Toniann Pitassi)

                 Matrix Sparsification for Rank and Determinant Computations via Nested Dissection
                 Raphael Yuster

                 Fast Modular Composition in any Characteristic
                 Kiran S. Kedlaya and Christopher Umans

                 Gaussian Bounds for Noise Correlation of Functions and Tight Analysis of Long Codes
                 Elchanan Mossel

                 Worst Case to Average Case Reductions for Polynomials
                 Tali Kaufman and Shachar Lovett

     Lunch 12:20--2:00pm

     Session 3 2:00--3:10pm

         Session 3A (Session Chair: Jeff Erickson)

         On the Union of Cylinders in Three Dimensions
         Esther Ezra

         Spherical Cubes and Rounding in High Dimensions
         Guy Kindler, Ryan O'Donnell, Anup Rao, and Avi Wigderson

         Near-Optimal Sparse Recovery in the L1 Norm
         Piotr Indyk and Milan Ruzic

                 Session 3B (Session Chair: Avrim Blum)

                 On Basing Lower-Bounds for Learning on Worst-Case Assumptions
                 Benny Applebaum, Boaz Barak, and David Xiao

                 The Bayesian Learner is Optimal for Noisy Binary Search (and Pretty Good for Quantum as Well)
                 Michael Ben-Or and Avinatan Hassidim

                 Hardness of Minimizing and Learning DNF Expressions
                 Subhash Khot and Rishi Saket

     Break 3:10--3:40pm

     Session 4 3:40--4:50pm

         Session 4A (Session Chair: Yossi Azar)

         Elections Can be Manipulated Often
         Ehud Friedgut, Gil Kalai, and Noam Nisan

         On the Hardness of Being Truthful
         Christos Papadimitriou, Michael Schapira, and Yaron Singer

         Multi-unit Auctions with Budget Limits
         Shahar Dobzinski, Ron Lavi, and Noam Nisan

                 Session 4B (Session Chair: Yevgeniy Dodis)

                 Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors
                 Ran Raz and Amir Yehudayoff

                 On the Impossibility of Basing Identity Based Encryption on Trapdoor Permutations
                 Dan Boneh, Periklis Papakonstantinou, Charles Rackoff, Yevgeniy Vahlis, and Brent Waters

                 Leakage-Resilient Cryptography
                 Stefan Dziembowski and Krzysztof Pietrzak

     Session 5 5:15--6:15pm (Session Chair: R. Ravi)

         Succincter
         Mihai Patrascu

         Two Query PCP with Sub-Constant Error
         Dana Moshkovitz and Ran Raz

     Business Meeting 9:00pm

Monday, 27th Oct.

         Session 6A (Session Chair: Yury Makarychev)

         Constant-Time Approximation Algorithms via Local Improvements
         Huy N. Nguyen and Krzysztof Onak

         Some Results on Greedy Embeddings in Metric Spaces
         Ankur Moitra and Tom Leighton

         Set Covering with our Eyes Closed
         Fabrizio Grandoni, Anupam Gupta, Stefano Leonardi, Pauli Miettinen, Piotr Sankowski, and Mohit Singh

         Minimizing Movement in Mobile Facility Location Problems
         Zachary Friggstad and Mohammad R. Salavatipour

                 Session 6B (Session Chair: Sampath Kannan)

                 A Counterexample to Strong Parallel Repetition
                 Ran Raz

                 Rounding Parallel Repetitions of Unique Games
                 Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, and David Steurer

                 The Unbounded-Error Communication Complexity of Symmetric Functions
                 Alexander A. Sherstov

                 Lower Bounds for Noisy Wireless Networks using Sampling Algorithms
                 Chinmoy Dutta and Jaikumar Radhakrishnan

     Session 7 10:45am--12:20pm

         Session 7A (Session Chair: Jeff Erickson)

         Inapproximability for Metric Embeddings into R^d
         Jiri Matousek and Anastasios Sidiropoulos

         A Geometric Approach to Lower Bounds for Approximate Near-Neighbor Search and Partial Match
         Rina Panigrahy, Kunal Talwar, and Udi Wieder

         Hardness of Nearest Neighbor under L-infinity
         Alexandr Andoni, Dorian Croitoru, and Mihai Patrascu

         (Data) STRUCTURES
         Mihai Patrascu

                 Session 7B (Session Chair: Scott Aaronson)

                 Entangled Games are Hard to Approximate
                 Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, and Thomas Vidick

                 Unique Games with Entangled Provers are Easy
                 Julia Kempe, Oded Regev, and Ben Toner

                 Quantum Multi Prover Interactive Proofs with Communicating Provers
                 Michael Ben Or, Avinatan Hassidim, and Haran Pilpel

                 A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs
                 Avraham Ben-Aroya, Oded Regev, and Ronald de Wolf

     Lunch 12:20--2:00pm

     Session 8 2:00pm--3:35pm

         Session 8A (Session Chair: Artur Czumaj)

         Sketching and Streaming Entropy via Approximation Theory
         Nicholas J.A. Harvey, Jelani Nelson, and Krzysztof Onak

         On the Value of Multiple Read/Write Streams for Approximating Frequency Moments
         Paul Beame and Dang-Trinh Huynh-Ngoc

         Clock Synchronization with Bounded Global and Local Skew
         Christoph Lenzen, Thomas Locher, and Roger Wattenhofer

         Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners
         Yefim Dinitz, Michael Elkin, and Shay Solomon

                 Session 8B (Session Chair: Yishay Mansour)

                 What Can We Learn Privately?
                 Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith

                 Learning Geometric Concepts via Gaussian Surface Area
                 Adam R. Klivans, Ryan O\u2019Donnell, and Rocco A. Servedio

                 Isotropic PCA and Affine-Invariant Clustering
                 Spencer Charles Brubaker and Santosh Vempala

                 Approximate Kernel Clustering
                 Subhash Khot and Assaf Naor

     Break 3:35--4:00pm

     Session 9 4:00--5:35pm

         Session 9A (Session Chair: Yossi Azar)

         Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph
         Venkatesan Guruswami, Rajsekar Manokaran, and Prasad Raghavendra

         (Acyclic) Job Shops are Hard to Approximate
         Monaldo Mastrolilli and Ola Svensson

         Linear Level Lasserre Lower Bounds for Certain k-CSPs
         Grant Schoenebeck

         The Power of Reordering for Online Minimum Makespan Scheduling
         Matthias Englert, Deniz �zmen, and Matthias Westermann

         Locally Testing Direct Product in the Low Error Range
         Irit Dinur and Elazar Goldenberg

                 Session 9B (Session Chair: Valerie King)

                 Kakeya Sets, New Mergers and Old Extractors
                 Zeev Dvir and Avi Wigderson

                 A Dichotomy Theorem for the Resolution Complexity of Random Constraint Satisfaction Problems
                 Siu On Chan and Michael Molloy

                 Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness
                 Jin-Yi Cai, Pinyan Lu, and Mingji Xia

                 Network Extractor Protocols
                 Yael Tauman Kalai, Xin Li, Anup Rao, and David Zuckerman

Tuesday, 28th Oct.

     Session 10 8:40am--10:15pm

         Session 10A (Session Chair: Yury Makarychev)

         Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time
         Laszlo Babai and Paolo Codenotti

         Computing the Tutte Polynomial in Vertex-Exponential Time
         Andreas Bj�rklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto

         On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP
         Deeparnab Chakrabarty and Gagan Goel

         Submodular Approximation: Sampling-based Algorithms and Lower Bounds
         Zoya Svitkina and Lisa Fleischer

                 Session 10B (Session Chair: Jonathan Katz)

                 Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution
                 Eli Ben-Sasson and Jakob Nordstr�m

                 Noise Tolerance of Expanders and Sublinear Expander Reconstruction
                 Satyen Kale, Yuval Peres, and C. Seshadhri

                 Sequence Length Requirement of Distance-Based Phylogeny Reconstruction: Breaking the Polynomial Barrier
                 S�bastien Roch

                 Size Bounds and Query Plans for Relational Joins
                 Albert Atserias, Martin Grohe, and D�niel Marx

     Break 10:15--10:45am

     Session 11 10:45am--12:20pm

         Session 11A (Session Chair: Rafail Ostrovsky)

         Eigenvalue Bounds, Spectral Partitioning, and Metrical Deformations via Flows
         Punyashloka Biswal, James R. Lee, and Satish Rao

         Embeddings of Topological Graphs: Lossy Invariants, Linearization, and 2-Sums
         Amit Chakrabarti, Alexander Jaffe, James R. Lee, and Justin Vincent

         A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width
         Ken-ichi Kawarabayashi, Bojan Mohar, and Bruce Reed

         Nearly Tight Low Stretch Spanning Trees
         Ittai Abraham, Yair Bartal, and Ofer Neiman

                 Session 11B (Session Chair: Harry Buhrman)

                 Algorithmic Barriers from Phase Transitions
                 Dimitris Achlioptas and Amin Coja-Oghlan

                 Mixing Time of Exponential Random Graphs
                 Shankar Bhamidi, Guy Bresler, and Allan Sly

                 k-Wise Independent Random Graphs
                 Noga Alon and Asaf Nussboim

                 Broadcasting with Side Information
                 Noga Alon, Eyal Lubetzky, Uri Stav, Amit Weinstein, and Avinatan Hassidim

     Conference Ends

IEEE CS | ACM | SIGACT | IRA 2008 | SODA '08 | STOC '08 | SODA '07 | STOC '07 | FOCS '07