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
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
Metric Embeddings with Relaxed Guarantees, Ittai Abraham, Yair Bartal, T-H. Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon Kleinberg, Ofer Neiman, and Aleksandrs Slivkins
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
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
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
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




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
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
Almost Orthogonal Linear Codes are Locally Testable, Tali Kaufman and Simon Litsyn
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
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
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





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
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
Analysis and Prediction of the Long-Run Behavior of Probabilistic Sequential Programs with Recursion, Tomas Brázdil and Javier Esparza and Antonin Kučera
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
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
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
A Tale of Two Dimensional Bin Packing, Nikhil Bansal and Andrea Lodi and Maxim Sviridenko