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