## List of paper accepted for Presentation for FOCS 2005

• The Closest Substring problem with small distances, Dániel Marx
• A Characterization of the (natural) Graph Properties Testable with One-Sided Error, Noga Alon and Asaf Shapira
• Answering distance queries in directed graphs using fast matrix multiplication, Raphael Yuster and Uri Zwick
• Additive Approximation for Edge-Deletion Problems, Noga Alon and Asaf Shapira and Benny Sudakov
• Analysis and Prediction of the Long-Run Behavior of Probabilistic Sequential Programs with Recursion, Tomas Brazdil and Javier Esparza and Antonin Kucera
• Approximation Algorithms for Unique Games, Luca Trevisan
• The Symmetric Group Defies Strong Fourier Sampling, Cristopher Moore and Alexander Russell and Leonard J. Schulman
• Almost Orthogonal Linear Codes are Locally Testable, Tali Kaufman and Simon Litsyn
• Cryptography in the Bounded Quantum-Storage Model, Ivan Damgaard and Serge Fehr and Louis Salvail and Christian Schaffner
• An algorithmic version of the hypergraph regularity method, P. Haxell and B. Nagle and V. Rodl
• A Recursive Greedy Algorithm for Walks in Directed Graphs, Chandra Chekuri and Martin Pal
• A Randomness-Efficient Sampler for Matrix-valued Functions and Applications, Avi Wigderson and David Xiao
• Quantum Information and the PCP Theorem , Ran Raz
• Structuring labeled trees for optimal succinctness, and beyond, P. Ferragina and F. Luccio and G. Manzini and S. Muthukrishnan
• Nonembeddability theorems via Fourier analysis, Subhash Khot and Assaf Naor
• Safraless Decision Procedures, Orna Kupferman and Moshe Y. Vardi
• Approximation Algorithms and Mechanism Design for Scheduling on Multiple Machines, V. S. Anil Kumar and Madhav V. Marathe and Srinivasan Parthasarathy and Aravind Srinivasan
• Query Incentive Networks, Jon Kleinberg and Prabhakar Raghavan
• An Approximation Algorithm for the Disjoint Paths Problem in Even-Degree Planar Graphs, Jon Kleinberg
• The Complexity of Online Memory Checking, Moni Naor and Guy N. Rothblum
• 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
• Noise stability of functions with low influences: invariance and optimality, Elchanan Mossel and Ryan O'Donnell and Krzysztof Oleszkiewicz
• Group-theoretic Algorithms for Matrix Multiplication, Henry Cohn and Robert Kleinberg and Balazs Szegedy and Christopher Umans
• Deterministic Extractors for Affine Sources over Large Fields, Ariel Gabizon and Ran Raz
• On the Complexity of Two-Player Win-Lose Games, Tim Abbott and Daniel Kane and Paul Valiant
• On the Complexity of Real Functions, Mark Braverman
• A general lower bound for mixing of single-site dynamics on graphs, Thomas P. Hayes and Alistair Sinclair
• Metric Embeddings with Relaxed Guarantees, Ittai Abraham, Yair Bartal, T-H. Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon Kleinberg, Ofer Neiman, and Aleksandrs Slivkins
• Towards a Final Analysis of Pairing Heaps, Seth Pettie
• On Learning Mixtures of Heavy-Tailed Distributions, Anirban Dasgupta and John Hopcroft and Jon Kleinberg and Mark Sandler
• Learning mixtures of product distributions over discrete domains, Jon Feldman and Ryan O'Donnell and Rocco A. Servedio
• Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring, Erik D. Demaine and MohammadTaghi Hajiaghayi and Ken-ichi Kawarabayashi
• A Tale of Two Dimensional Bin Packing, Nikhil Bansal and Andrea Lodi and Maxim Sviridenko
• The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into $\ell_1$, Subhash Khot, Nisheeth Vishnoi
• Linear Lower Bounds on Real-World Implementations of Concurrent Objects, Faith Ellen Fich, Danny Hendler, Nir Shavit
• Sampling-based Approximation Algorithms for Multi-Stage Stochastic Optimization,  Chaitanya Swamy and David B. Shmoys
• How To Play Almost Any Mental Game Over the Net -Concurrent Composition via Super-Polynomial Simulation, Boaz Barak and Amit Sahai
• Nash Equilibria in Random Games, Imre Barany and Santosh Vempala and Adrian Vetta
• Sink Equilibria and Convergence, Vahab Mirrokni and Adrian Vetta
• Every decision tree has an influential variable , Ryan O'Donnell and Michael Saks and Oded Schramm and Rocco Servedio
• Truthful and Near-optimal Mechanism Design via Linear Programming, Ron Lavi and Chaitanya Swamy
• Agnostically Learning Halfspaces, Adam Kalai and Adam Klivans and Yishay Mansour and Rocco Servedio
• Hardness of Undirected Edge Disjoint Paths with Congestion, Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna, and Lisa Zhang
• Concurrent Non-Malleable Commitments, Rafael Pass and Alon Rosen
• The Parking Permit Problem, Adam Meyerson
• Mechanism Design via Machine Learning, Maria-Florina Balcan and Avrim Blum and Jason Hartline and Yishay Mansour
• On the Impossibility of Obfuscation with Auxiliary Inputs, Shafi Goldwasser and Yael Tauman Kalai
• How to Pay, Come What May : Approximation Algorithms for Demand-Robust Covering Problems, Kedar Dhamdhere and Vineet Goyal and R. Ravi and Mohit Singh
• Improved Smoothed Analysis of the Shadow Vertex Simplex Method, Amit Deshpande and Daniel A. Spielman
• Beyond VCG: Frugality of Truthful Mechanisms, Anna R. Karlin and David Kempe and Tami Tamir
• Fitting tree metrics: Hierarchical clustering and Phylogeny, Nir Ailon and Moses Charikar
• Error-Correcting Codes for Automatic Control, Rafail Ostrovsky and Yuval Rabani and Leonard J. Schulman
• On Non-Approximability for Quadratic Programs, Sanjeev Arora and Eli Berger and Elad Hazan and Guy Kindler and Muli Safra
• A linear-time approximation scheme for planar weighted TSP, Philip N. Klein
• Fast Algorithms for Approximate Semidefinite Programming using the Multiplicative Weights Update Method, Sanjeev Arora and Elad Hazan and Satyen Kale
• AdWords and Generalized On-line Matching, Aranyak Mehta and Amin Saberi and Umesh Vazirani and Vijay Vazirani
• Hardness of Approximating the Closest Vector Problem with Pre-Processing, Mikhail Alekhnovich and Subhash A. Khot and Guy Kindler and Nisheeth K. Vishnoi
• Universal Mechanism Design, Sergei Izmalkov, Matt Lepinski and Silvio Micali
• Lower-bounds for the noisy broadcast model, and for generalized noisy-decision trees, Navin Goyal and Guy Kindler and Michael Saks
• Correcting Errors Beyond the Guruswami-Sudan Radius in Polynomial Time, Farzad Parvaresh and Alexander Vardy
• On Delsarte's Linear Programming Bounds for Binary Codes, Michael Navon and Alex Samorodnitsky
• Error Correction via Linear Programming. Emmanuel J. Candes and Mark Rudelson and Terence Tao and Roman Vershynin.
•