46. FOCS 2005: Pittsburgh, PA, USA

46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings. IEEE Computer Society 2005, ISBN 0-7695-2468-0 BibTeX

Cover

FOCS 2005 - Title Page.
Electronic Edition (link) BibTeX
FOCS 2005 - Copyright.
Electronic Edition (link) BibTeX

Introduction

Foreword.
Electronic Edition (link) BibTeX
Committees.
Electronic Edition (link) BibTeX
Best Paper Awards.
Electronic Edition (link) BibTeX
Machtey Award.
Electronic Edition (link) BibTeX
Knuth Prize.
Electronic Edition (link) BibTeX
Reviewers.
Electronic Edition (link) BibTeX
Corporate Sponsors.
Electronic Edition (link) BibTeX

Tutorial 1

Subhash Khot:
On the Unique Games Conjecture. 3
Electronic Edition (link) BibTeX

Tutorial 2

Bernard Chazelle:
Algorithmic Techniques and Tools from Computational Geometry. 7
Electronic Edition (link) BibTeX

Session 1

Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, Rocco A. Servedio:
Agnostically Learning Halfspaces. 11-20
Electronic Edition (link) BibTeX
Elchanan Mossel, Ryan O'Donnell, Krzysztof Oleszkiewicz:
Noise stability of functions with low in.uences invariance and optimality. 21-30
Electronic Edition (link) BibTeX
Ryan O'Donnell, Michael E. Saks, Oded Schramm, Rocco A. Servedio:
Every decision tree has an in.uential variable. 31-39
Electronic Edition (link) BibTeX
Navin Goyal, Guy Kindler, Michael E. Saks:
Lower Bounds for the Noisy Broadcast Problem. 40-52
Electronic Edition (link) BibTeX

Session 2: Best Paper Award

Subhash Khot, Nisheeth K. Vishnoi:
The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into l₁. 53-62
Electronic Edition (link) BibTeX
Dániel Marx:
The Closest Substring problem with small distances. 63-72
Electronic Edition (link) BibTeX
Nir Ailon, Moses Charikar:
Fitting tree metrics: Hierarchical clustering and Phylogeny. 73-82
Electronic Edition (link) BibTeX
Ittai Abraham, Yair Bartal, Hubert T.-H. Chan, Kedar Dhamdhere, Anupam Gupta, Jon M. Kleinberg, Ofer Neiman, Aleksandrs Slivkins:
Metric Embeddings with Relaxed Guarantees. 83-100
Electronic Edition (link) BibTeX
Subhash Khot, Assaf Naor:
Nonembeddability theorems via Fourier analysis. 101-112
Electronic Edition (link) BibTeX

Session 3 Machtey Award

Timothy G. Abbott, Daniel Kane, Paul Valiant:
On the Complexity of Two-PlayerWin-Lose Games. 113-122
Electronic Edition (link) BibTeX
Imre Bárány, Santosh Vempala, Adrian Vetta:
Nash Equilibria in Random Games. 123-131
Electronic Edition (link) BibTeX
Jon M. Kleinberg, Prabhakar Raghavan:
Query Incentive Networks. 132-141
Electronic Edition (link) BibTeX
Michel X. Goemans, Vahab S. Mirrokni, Adrian Vetta:
Sink Equilibria and Convergence. 142-154
Electronic Edition (link) BibTeX

Session 4 Machtey Award Paper

Mark Braverman:
On the Complexity of Real Functions. 155-164
Electronic Edition (link) BibTeX
Faith Ellen Fich, Danny Hendler, Nir Shavit:
Linear Lower Bounds on Real-World Implementations of Concurrent Objects. 165-173
Electronic Edition (link) BibTeX
Seth Pettie:
Towards a Final Analysis of Pairing Heaps. 174-183
Electronic Edition (link) BibTeX
Paolo Ferragina, Fabrizio Luccio, Giovanni Manzini, S. Muthukrishnan:
Structuring labeled trees for optimal succinctness, and beyond. 184-196
Electronic Edition (link) BibTeX

Session 5

Luca Trevisan:
Approximation Algorithms for Unique Games. 197-205
Electronic Edition (link) BibTeX
Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra:
On Non-Approximability for Quadratic Programs. 206-215
Electronic Edition (link) BibTeX
Mikhail Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi:
Hardness of Approximating the Closest Vector Problem with Pre-Processing. 216-225
Electronic Edition (link) BibTeX
Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna, Lisa Zhang:
Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion. 226-244
Electronic Edition (link) BibTeX

Session 6

Chandra Chekuri, Martin Pál:
A Recursive Greedy Algorithm for Walks in Directed Graphs. 245-253
Electronic Edition (link) BibTeX
V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan:
Approximation Algorithms for Scheduling on Multiple Machines. 254-263
Electronic Edition (link) BibTeX
Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, Vijay V. Vazirani:
AdWords and Generalized On-line Matching. 264-273
Electronic Edition (link) BibTeX
Adam Meyerson:
The Parking Permit Problem. 274-284
Electronic Edition (link) BibTeX

Session 7 Best Paper Award

Farzad Parvaresh, Alexander Vardy:
Correcting Errors Beyond the Guruswami-Sudan Radius in Polynomial Time. 285-294
Electronic Edition (link) BibTeX
Emmanuel J. Candès, Mark Rudelson, Terence Tao, Roman Vershynin:
Error Correction via Linear Programming. 295-308
Electronic Edition (link) BibTeX
Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman:
Error-Correcting Codes for Automatic Control. 309-316
Electronic Edition (link) BibTeX
Tali Kaufman, Simon Litsyn:
Almost Orthogonal Linear Codes are Locally Testable. 317-326
Electronic Edition (link) BibTeX
Michael Navon, Alex Samorodnitsky:
On Delsarte's Linear Programming Bounds for Binary Codes. 327-338
Electronic Edition (link) BibTeX

Session 8

Sanjeev Arora, Elad Hazan, Satyen Kale:
Fast Algorithms for Approximate Semide.nite Programming using the Multiplicative Weights Update Method. 339-348
Electronic Edition (link) BibTeX
Amit Deshpande, Daniel A. Spielman:
Improved Smoothed Analysis of the Shadow Vertex Simplex Method. 349-356
Electronic Edition (link) BibTeX
Chaitanya Swamy, David B. Shmoys:
Sampling-based Approximation Algorithms for Multi-stage Stochastic. 357-366
Electronic Edition (link) BibTeX
Kedar Dhamdhere, Vineet Goyal, R. Ravi, Mohit Singh:
How to Pay, Come What May: Approximation Algorithms for Demand-Robust Covering Problems. 367-378
Electronic Edition (link) BibTeX

Session 9

Henry Cohn, Robert D. Kleinberg, Balázs Szegedy, Christopher Umans:
Group-theoretic Algorithms for Matrix Multiplication. 379-388
Electronic Edition (link) BibTeX
Raphael Yuster, Uri Zwick:
Answering distance queries in directed graphs using fast matrix multiplication. 389-396
Electronic Edition (link) BibTeX
Avi Wigderson, David Xiao:
A Randomness-Efficient Sampler for Matrix-valued Functions and Applications. 397-406
Electronic Edition (link) BibTeX
Ariel Gabizon, Ran Raz:
Deterministic Extractors for Affine Sources over Large Fields. 407-418
Electronic Edition (link) BibTeX

Session 10

Noga Alon, Asaf Shapira, Benny Sudakov:
Additive Approximation for Edge-Deletion Problems. 419-428
Electronic Edition (link) BibTeX
Noga Alon, Asaf Shapira:
A Characterization of the (natural) Graph Properties Testable with One-Sided Error. 429-438
Electronic Edition (link) BibTeX
Penny E. Haxell, Brendan Nagle, Vojtech Rödl:
An Algorithmic Version of the Hypergraph Regularity Method. 439-448
Electronic Edition (link) BibTeX

Session 11

Ivan Damgård, Serge Fehr, Louis Salvail, Christian Schaffner:
Cryptography In the Bounded Quantum-Storage Model. 449-458
Electronic Edition (link) BibTeX
Ran Raz:
Quantum Information and the PCP Theorem. 459-468
Electronic Edition (link) BibTeX
Dave Bacon, Andrew M. Childs, Wim van Dam:
From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups. 469-478
Electronic Edition (link) BibTeX
Cristopher Moore, Alexander Russell, Leonard J. Schulman:
The Symmetric Group Defies Strong Fourier Sampling. 479-490
Electronic Edition (link) BibTeX

Session 12

Anirban Dasgupta, John E. Hopcroft, Jon M. Kleinberg, Mark Sandler:
On Learning Mixtures of Heavy-Tailed Distributions. 491-500
Electronic Edition (link) BibTeX
Jon Feldman, Ryan O'Donnell, Rocco A. Servedio:
Learning mixtures of product distributions over discrete domains. 501-510
Electronic Edition (link) BibTeX
Thomas P. Hayes, Alistair Sinclair:
A general lower bound for mixing of single-site dynamics on graphs. 511-520
Electronic Edition (link) BibTeX
Tomás Brázdil, Javier Esparza, Antonín Kucera:
Analysis and Prediction of the Long-Run Behavior of Probabilistic Sequential Programs with Recursion (Extended Abstract). 521-530
Electronic Edition (link) BibTeX
Orna Kupferman, Moshe Y. Vardi:
Safraless Decision Procedures. 531-542
Electronic Edition (link) BibTeX

Session 13

Boaz Barak, Amit Sahai:
How To Play Almost Any Mental Game Over The Net - Concurrent Composition via Super-Polynomial Simulation. 543-552
Electronic Edition (link) BibTeX
Shafi Goldwasser, Yael Tauman Kalai:
On the Impossibility of Obfuscation with Auxiliary Input. 553-562
Electronic Edition (link) BibTeX
Rafael Pass, Alon Rosen:
Concurrent Non-Malleable Commitments. 563-572
Electronic Edition (link) BibTeX
Moni Naor, Guy N. Rothblum:
The Complexity of Online Memory Checking. 573-584
Electronic Edition (link) BibTeX

Session 14

Sergei Izmalkov, Silvio Micali, Matt Lepinski:
Rational Secure Computation and Ideal Mechanism Design. 585-595
Electronic Edition (link) BibTeX
Ron Lavi, Chaitanya Swamy:
Truthful and Near-Optimal Mechanism Design via Linear Programming. 595-604
Electronic Edition (link) BibTeX
Maria-Florina Balcan, Avrim Blum, Jason D. Hartline, Yishay Mansour:
Mechanism Design via Machine Learning. 605-614
Electronic Edition (link) BibTeX
Anna R. Karlin, David Kempe, Tami Tamir:
Beyond VCG: Frugality of Truthful Mechanisms. 615-626
Electronic Edition (link) BibTeX

Session 15

Jon M. Kleinberg:
An Approximation Algorithm for the Disjoint Paths Problem in Even-Degree Planar Graphs. 627-636
Electronic Edition (link) BibTeX
Erik D. Demaine, Mohammad Taghi Hajiaghayi, Ken-ichi Kawarabayashi:
Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring. 637-646
Electronic Edition (link) BibTeX
Philip N. Klein:
A linear-time approximation scheme for planar weighted TSP. 647-657
Electronic Edition (link) BibTeX
Nikhil Bansal, Andrea Lodi, Maxim Sviridenko:
A Tale of Two Dimensional Bin Packing. 657-666
Electronic Edition (link) BibTeX