| 2005 | 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005, Pittsburgh, PA, USA, October 23-25, 2005, Proceedings |
| 2005 | A Characterization of the (natural) Graph Properties Testable with One-Sided Error. Noga Alon, Asaf Shapira |
| 2005 | A Randomness-Efficient Sampler for Matrix-valued Functions and Applications. Avi Wigderson, David Xiao |
| 2005 | A Recursive Greedy Algorithm for Walks in Directed Graphs. Chandra Chekuri, Martin Pál |
| 2005 | A Tale of Two Dimensional Bin Packing. Nikhil Bansal, Andrea Lodi, Maxim Sviridenko |
| 2005 | A general lower bound for mixing of single-site dynamics on graphs. Thomas P. Hayes, Alistair Sinclair |
| 2005 | A linear-time approximation scheme for planar weighted TSP. Philip N. Klein |
| 2005 | AdWords and Generalized On-line Matching. Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, Vijay V. Vazirani |
| 2005 | Additive Approximation for Edge-Deletion Problems. Noga Alon, Asaf Shapira, Benny Sudakov |
| 2005 | Agnostically Learning Halfspaces. Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, Rocco A. Servedio |
| 2005 | Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring. Erik D. Demaine, Mohammad Taghi Hajiaghayi, Ken-ichi Kawarabayashi |
| 2005 | Algorithmic Techniques and Tools from Computational Geometry. Bernard Chazelle |
| 2005 | Almost Orthogonal Linear Codes are Locally Testable. Tali Kaufman, Simon Litsyn |
| 2005 | An Algorithmic Version of the Hypergraph Regularity Method. Penny E. Haxell, Brendan Nagle, Vojtech Rödl |
| 2005 | An Approximation Algorithm for the Disjoint Paths Problem in Even-Degree Planar Graphs. Jon M. Kleinberg |
| 2005 | Analysis and Prediction of the Long-Run Behavior of Probabilistic Sequential Programs with Recursion (Extended Abstract). Tomás Brázdil, Javier Esparza, Antonín Kucera |
| 2005 | Answering distance queries in directed graphs using fast matrix multiplication. Raphael Yuster, Uri Zwick |
| 2005 | Approximation Algorithms for Scheduling on Multiple Machines. V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan |
| 2005 | Approximation Algorithms for Unique Games. Luca Trevisan |
| 2005 | Best Paper Awards. |
| 2005 | Beyond VCG: Frugality of Truthful Mechanisms. Anna R. Karlin, David Kempe, Tami Tamir |
| 2005 | Committees. |
| 2005 | Concurrent Non-Malleable Commitments. Rafael Pass, Alon Rosen |
| 2005 | Corporate Sponsors. |
| 2005 | Correcting Errors Beyond the Guruswami-Sudan Radius in Polynomial Time. Farzad Parvaresh, Alexander Vardy |
| 2005 | Cryptography In the Bounded Quantum-Storage Model. Ivan Damgård, Serge Fehr, Louis Salvail, Christian Schaffner |
| 2005 | Deterministic Extractors for Affine Sources over Large Fields. Ariel Gabizon, Ran Raz |
| 2005 | Error Correction via Linear Programming. Emmanuel J. Candès, Mark Rudelson, Terence Tao, Roman Vershynin |
| 2005 | Error-Correcting Codes for Automatic Control. Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman |
| 2005 | Every decision tree has an in.uential variable. Ryan O'Donnell, Michael E. Saks, Oded Schramm, Rocco A. Servedio |
| 2005 | FOCS 2005 - Copyright. |
| 2005 | FOCS 2005 - Title Page. |
| 2005 | Fast Algorithms for Approximate Semide.nite Programming using the Multiplicative Weights Update Method. Sanjeev Arora, Elad Hazan, Satyen Kale |
| 2005 | Fitting tree metrics: Hierarchical clustering and Phylogeny. Nir Ailon, Moses Charikar |
| 2005 | Foreword. |
| 2005 | From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups. Dave Bacon, Andrew M. Childs, Wim van Dam |
| 2005 | Group-theoretic Algorithms for Matrix Multiplication. Henry Cohn, Robert D. Kleinberg, Balázs Szegedy, Christopher Umans |
| 2005 | Hardness of Approximating the Closest Vector Problem with Pre-Processing. Mikhail Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi |
| 2005 | Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion. Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna, Lisa Zhang |
| 2005 | How To Play Almost Any Mental Game Over The Net - Concurrent Composition via Super-Polynomial Simulation. Boaz Barak, Amit Sahai |
| 2005 | How to Pay, Come What May: Approximation Algorithms for Demand-Robust Covering Problems. Kedar Dhamdhere, Vineet Goyal, R. Ravi, Mohit Singh |
| 2005 | Improved Smoothed Analysis of the Shadow Vertex Simplex Method. Amit Deshpande, Daniel A. Spielman |
| 2005 | Knuth Prize. |
| 2005 | Learning mixtures of product distributions over discrete domains. Jon Feldman, Ryan O'Donnell, Rocco A. Servedio |
| 2005 | Linear Lower Bounds on Real-World Implementations of Concurrent Objects. Faith Ellen Fich, Danny Hendler, Nir Shavit |
| 2005 | Lower Bounds for the Noisy Broadcast Problem. Navin Goyal, Guy Kindler, Michael E. Saks |
| 2005 | Machtey Award. |
| 2005 | Mechanism Design via Machine Learning. Maria-Florina Balcan, Avrim Blum, Jason D. Hartline, Yishay Mansour |
| 2005 | Metric Embeddings with Relaxed Guarantees. Ittai Abraham, Yair Bartal, T.-H. Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon M. Kleinberg, Ofer Neiman, Aleksandrs Slivkins |
| 2005 | Nash Equilibria in Random Games. Imre Bárány, Santosh S. Vempala, Adrian Vetta |
| 2005 | Noise stability of functions with low in.uences invariance and optimality. Elchanan Mossel, Ryan O'Donnell, Krzysztof Oleszkiewicz |
| 2005 | Nonembeddability theorems via Fourier analysis. Subhash Khot, Assaf Naor |
| 2005 | On Delsarte's Linear Programming Bounds for Binary Codes. Michael Navon, Alex Samorodnitsky |
| 2005 | On Learning Mixtures of Heavy-Tailed Distributions. Anirban Dasgupta, John E. Hopcroft, Jon M. Kleinberg, Mark Sandler |
| 2005 | On Non-Approximability for Quadratic Programs. Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra |
| 2005 | On the Complexity of Real Functions. Mark Braverman |
| 2005 | On the Complexity of Two-PlayerWin-Lose Games. Timothy G. Abbott, Daniel Kane, Paul Valiant |
| 2005 | On the Impossibility of Obfuscation with Auxiliary Input. Shafi Goldwasser, Yael Tauman Kalai |
| 2005 | On the Unique Games Conjecture. Subhash Khot |
| 2005 | Quantum Information and the PCP Theorem. Ran Raz |
| 2005 | Query Incentive Networks. Jon M. Kleinberg, Prabhakar Raghavan |
| 2005 | Rational Secure Computation and Ideal Mechanism Design. Sergei Izmalkov, Silvio Micali, Matt Lepinski |
| 2005 | Reviewers. |
| 2005 | Safraless Decision Procedures. Orna Kupferman, Moshe Y. Vardi |
| 2005 | Sampling-based Approximation Algorithms for Multi-stage Stochastic. Chaitanya Swamy, David B. Shmoys |
| 2005 | Sink Equilibria and Convergence. Michel X. Goemans, Vahab S. Mirrokni, Adrian Vetta |
| 2005 | Structuring labeled trees for optimal succinctness, and beyond. Paolo Ferragina, Fabrizio Luccio, Giovanni Manzini, S. Muthukrishnan |
| 2005 | The Closest Substring problem with small distances. Dániel Marx |
| 2005 | The Complexity of Online Memory Checking. Moni Naor, Guy N. Rothblum |
| 2005 | The Parking Permit Problem. Adam Meyerson |
| 2005 | The Symmetric Group Defies Strong Fourier Sampling. Cristopher Moore, Alexander Russell, Leonard J. Schulman |
| 2005 | The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into l Subhash Khot, Nisheeth K. Vishnoi |
| 2005 | Towards a Final Analysis of Pairing Heaps. Seth Pettie |
| 2005 | Truthful and Near-Optimal Mechanism Design via Linear Programming. Ron Lavi, Chaitanya Swamy |