FOCS 2005 Program
| SATURDAY (tutorials held at CMU, travel directions here): |
The tutorials will be co-located with the second day of the Frieze Fest, that also offers many interesting talks, that are open to all FOCS participants.
1:30-3:30: Tutorial 1: (McConomy Auditorium, University Center, CMU) Chair Irit Dinur
On the Unique Games Conjecture, Subhash Khot
3:30-4:00 break
4:00-6:00 Tutorial 2: (Rangos 2&3, University Center, CMU)
Chair Sariel
Har-Peled
Algorithmic Techniques and Tools from Computational Geometry, Bernard Chazelle
7:00-9:00 Reception (at the Omni William Penn Hotel)
| SUNDAY (talks at the Grand Ballroom, 17th floor of the hotel): |
8:50-10:10 Session 1: Chair Éva Tardos
| 8:50 | Agnostically Learning Halfspaces, Adam Kalai and Adam Klivans and Yishay Mansour and Rocco Servedio |
| 9:10 | Noise stability of functions with low influences: invariance and optimality, Elchanan Mossel and Ryan O'Donnell and Krzysztof Oleszkiewicz |
| 9:30 | Every decision tree has an influential variable , Ryan O'Donnell and Michael Saks and Oded Schramm and Rocco Servedio |
| 9:50 | Lower Bounds for the Noisy Broadcast Problem, Navin Goyal and Guy Kindler and Michael Saks |
10:10-10:30 break
10:30-12:10 Session 2: Chair
Satish Rao
| 10:30 | The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into L1, Subhash Khot, Nisheeth Vishnoi |
| 10:50 | The Closest Substring problem with small distances, Dniel Marx |
| 11:10 | Fitting tree metrics: Hierarchical clustering and Phylogeny, Nir Ailon and Moses Charikar |
| 11:30 | Metric Embeddings with Relaxed Guarantees, Ittai Abraham, Yair Bartal, T-H. Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon Kleinberg, Ofer Neiman, and Aleksandrs Slivkins |
| 11:50 | Nonembeddability theorems via Fourier analysis, Subhash Khot and Assaf Naor |
12:10-1:30 lunch
1:30-2:50 Session 3: Chair Ashish
Goel
| 1:30 | On the Complexity of Two-Player Win-Lose Games, Tim Abbott and Daniel Kane and Paul Valiant |
| 1:50 | Nash Equilibria in Random Games, Imre Bárány and Santosh Vempala and Adrian Vetta |
| 2:10 | Query Incentive Networks, Jon Kleinberg and Prabhakar Raghavan |
| 2:30 | Sink Equilibria and Convergence, Michel Goemans, Vahab Mirrokni, and Adrian Vetta |
2:50-3:10 break
3:10-4:30 Session: Chair
Paul Beame
| 3:10 | On the Complexity of Real Functions, Mark Braverman |
| 3:30 | Linear Lower Bounds on Real-World Implementations of Concurrent Objects, Faith Ellen Fich, Danny Hendler, Nir Shavit |
| 3:50 | Towards a Final Analysis of Pairing Heaps, Seth Pettie |
| 4:10 | Structuring labeled trees for optimal succinctness, and beyond, P. Ferragina and F. Luccio and G. Manzini and S. Muthukrishnan |
4:30-4:50 break
4:50-6:10 Session 5: Chair
Irit Dinur
| 4:50 | Approximation Algorithms for Unique Games, Luca Trevisan |
| 5:10 | On Non-Approximability for Quadratic Programs, Sanjeev Arora and Eli Berger and Elad Hazan and Guy Kindler and Muli Safra |
| 5:30 | Hardness of Approximating the Closest Vector Problem with Pre-Processing, Mikhail Alekhnovich and Subhash A. Khot and Guy Kindler and Nisheeth K. Vishnoi |
| 5:50 | Hardness of the Undirected Edge-disjoint Paths Problem with Congestion, Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna, and Lisa Zhang |
8:30pm - 11:00pm. FOCS Business meeting and panel discussion
| Panel topic: | Exciting the public
about (theoretical) Computer Science
|
| Panelists: | Bernard Chazelle,
Richard Lipton, Ivars Peterson, Sara Robinson, Steven Rudich, Éva Tardos |
| MONDAY: |
8:50-10:10 Session 6: Chair Éva Tardos
| 8:50 | A Recursive Greedy Algorithm for Walks in Directed Graphs, Chandra Chekuri and Martin Pál |
| 9:10 | Approximation Algorithms for Scheduling on Multiple Machines, V. S. Anil Kumar and Madhav V. Marathe and Srinivasan Parthasarathy and Aravind Srinivasan |
| 9:30 | AdWords and Generalized On-line Matching, Aranyak Mehta and Amin Saberi and Umesh Vazirani and Vijay Vazirani |
| 9:50 | The Parking Permit Problem, Adam Meyerson |
10:10-10:30 break
10:30-12:10 Session 7: Chair
Venkatesan Guruswami
| 10:30 | Correcting Errors Beyond the Guruswami-Sudan Radius in Polynomial Time, Farzad Parvaresh and Alexander Vardy |
| 10:50 | Error Correction via Linear Programming. Emmanuel J. Candes and Mark Rudelson and Terence Tao and Roman Vershynin. |
| 11:10 | Error-Correcting Codes for Automatic Control, Rafail Ostrovsky and Yuval Rabani and Leonard J. Schulman |
| 11:30 | Almost Orthogonal Linear Codes are Locally Testable, Tali Kaufman and Simon Litsyn |
| 11:50 | On Delsarte's Linear Programming Bounds for Binary Codes, Michael Navon and Alex Samorodnitsky |
12:10-1:30 lunch
1:30-2:50 Session 8: Chair
Ashish Goel
| 1:30 | Fast Algorithms for Approximate Semidefinite Programming using the Multiplicative Weights Update Method, Sanjeev Arora and Elad Hazan and Satyen Kale |
| 1:50 | Improved Smoothed Analysis of the Shadow Vertex Simplex Method, Amit Deshpande and Daniel A. Spielman |
| 2:10 | Sampling-based Approximation Algorithms for Multi-Stage Stochastic Optimization, Chaitanya Swamy and David B. Shmoys |
| 2:30 | How to Pay, Come What May : Approximation Algorithms for Demand-Robust Covering Problems, Kedar Dhamdhere and Vineet Goyal and R. Ravi and Mohit Singh |
2:50-3:10 break
3:10-4:30 Session 9: Chair
David Zuckerman
| 3:10 | Group-theoretic Algorithms for Matrix Multiplication, Henry Cohn and Robert Kleinberg and Balazs Szegedy and Christopher Umans |
| 3:30 | Answering distance queries in directed graphs using fast matrix multiplication, Raphael Yuster and Uri Zwick |
| 3:50 | A Randomness-Efficient Sampler for Matrix-valued Functions and Applications, Avi Wigderson and David Xiao |
| 4:10 | Deterministic Extractors for Affine Sources over Large Fields, Ariel Gabizon and Ran Raz |
4:30-4:50 break
4:50-5:50 Session 10: Chair David Zuckerman
| 4:50 | Additive Approximation for Edge-Deletion Problems, Noga Alon and Asaf Shapira and Benny Sudakov |
| 5:10 | A Characterization of the (natural) Graph Properties Testable with One-Sided Error, Noga Alon and Asaf Shapira |
| 5:30 | An algorithmic version of the hypergraph regularity method, P. Haxell and B. Nagle and V. Rödl |
6:00-7:00 Knuth Prize Talk: Chair: Umesh Vazirani
Talk by the 2005 Knuth Prize winner: speaker and title TBA
| TUESDAY: |
8:50-10:10 Session 11: Chair John Watrous
| 8:50 | Cryptography in the Bounded Quantum-Storage Model, Ivan Damgärd and Serge Fehr and Louis Salvail and Christian Schaffner |
| 9:10 | Quantum Information and the PCP Theorem , Ran Raz |
| 9:30 | From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups, Dave Bacon and Andrew M. Childs and Wim van Dam |
| 9:50 | The Symmetric Group Defies Strong Fourier Sampling, Cristopher Moore and Alexander Russell and Leonard J. Schulman |
10:10-10:30 break
10:30-12:10 Session 12: Chair
Frank McSherry
| 10:30 | On Learning Mixtures of Heavy-Tailed Distributions, Anirban Dasgupta and John Hopcroft and Jon Kleinberg and Mark Sandler |
| 10:50 | Learning mixtures of product distributions over discrete domains, Jon Feldman and Ryan O'Donnell and Rocco A. Servedio |
| 11:10 | A general lower bound for mixing of single-site dynamics on graphs, Thomas P. Hayes and Alistair Sinclair |
| 11:30 | Analysis and Prediction of the Long-Run Behavior of Probabilistic Sequential Programs with Recursion, Tomas Brázdil and Javier Esparza and Antonin Kučera |
| 11:50 | Safraless Decision Procedures, Orna Kupferman and Moshe Y. Vardi |
12:10-1:30 lunch
1:30-2:50 Session 13: Chair
Richard Lipton
| 1:30 | How To Play Almost Any Mental Game Over the Net -Concurrent Composition via Super-Polynomial Simulation, Boaz Barak and Amit Sahai |
| 1:50 | On the Impossibility of Obfuscation with Auxiliary Inputs, Shafi Goldwasser and Yael Tauman Kalai |
| 2:10 | Concurrent Non-Malleable Commitments, Rafael Pass and Alon Rosen |
| 2:30 | The Complexity of Online Memory Checking, Moni Naor and Guy N. Rothblum |
2:50-3:10 break
3:10-4:30 Session 14: Chair
Richard Lipton
| 3:10 | Rational Secure Computation and Ideal Mechanism Design, Sergei Izmalkov, Matt Lepinski and Silvio Micali |
| 3:30 | Truthful and Near-optimal Mechanism Design via Linear Programming, Ron Lavi and Chaitanya Swamy |
| 3:50 | Mechanism Design via Machine Learning, Maria-Florina Balcan and Avrim Blum and Jason Hartline and Yishay Mansour |
| 4:10 | Beyond VCG: Frugality of Truthful Mechanisms, Anna R. Karlin and David Kempe and Tami Tamir |
4:30-4:50 break
4:50-6:10 Session 15: Chair
Mihalis Yannakakis
| 4:50 | An Approximation Algorithm for the Disjoint Paths Problem in Even-Degree Planar Graphs, Jon Kleinberg |
| 5:10 | Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring, Erik D. Demaine and MohammadTaghi Hajiaghayi and Ken-ichi Kawarabayashi |
| 5:30 | A linear-time approximation scheme for planar weighted TSP, Philip N. Klein |
| 5:50 | A Tale of Two Dimensional Bin Packing, Nikhil Bansal and Andrea Lodi and Maxim Sviridenko |