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
Cover
- FOCS 2005 - Title Page.
- FOCS 2005 - Copyright.
Introduction
- Foreword.
- Committees.
- Best Paper Awards.
- Machtey Award.
- Knuth Prize.
- Reviewers.
- Corporate Sponsors.
Tutorial 1
- Subhash Khot: On the Unique Games Conjecture. 3
Tutorial 2
- Bernard Chazelle: Algorithmic Techniques and Tools from Computational Geometry. 7
Session 1
- Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, Rocco A. Servedio: Agnostically Learning Halfspaces. 11-20
- Elchanan Mossel, Ryan O'Donnell, Krzysztof Oleszkiewicz: Noise stability of functions with low in.uences invariance and optimality. 21-30
- Ryan O'Donnell, Michael E. Saks, Oded Schramm, Rocco A. Servedio: Every decision tree has an in.uential variable. 31-39
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 l1. 53-62
- Dániel Marx: The Closest Substring problem with small distances. 63-72
- 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
Session 3 Machtey Award
- Timothy G. Abbott, Daniel M. Kane, Paul Valiant: On the Complexity of Two-PlayerWin-Lose Games. 113-122
Session 4 Machtey Award Paper
- Mark Braverman: On the Complexity of Real Functions. 155-164
- Faith Ellen Fich, Danny Hendler, Nir Shavit: Linear Lower Bounds on Real-World Implementations of Concurrent Objects. 165-173
- Seth Pettie: Towards a Final Analysis of Pairing Heaps. 174-183
- Paolo Ferragina, Fabrizio Luccio, Giovanni Manzini, S. Muthukrishnan: Structuring labeled trees for optimal succinctness, and beyond. 184-196
Session 5
- Luca Trevisan: Approximation Algorithms for Unique Games. 197-205
- Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra: On Non-Approximability for Quadratic Programs. 206-215
- Mikhail Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi: Hardness of Approximating the Closest Vector Problem with Pre-Processing. 216-225
- Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna, Lisa Zhang: Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion. 226-244
Session 6
- V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan: Approximation Algorithms for Scheduling on Multiple Machines. 254-263
- Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, Vijay V. Vazirani: AdWords and Generalized On-line Matching. 264-273
- Adam Meyerson: The Parking Permit Problem. 274-284
Session 7 Best Paper Award
- Farzad Parvaresh, Alexander Vardy: Correcting Errors Beyond the Guruswami-Sudan Radius in Polynomial Time. 285-294
- Emmanuel J. Candès, Mark Rudelson, Terence Tao, Roman Vershynin: Error Correction via Linear Programming. 295-308
- Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman: Error-Correcting Codes for Automatic Control. 309-316
- Michael Navon, Alex Samorodnitsky: On Delsarte's Linear Programming Bounds for Binary Codes. 327-338
Session 8
- Sanjeev Arora, Elad Hazan, Satyen Kale: Fast Algorithms for Approximate Semide.nite Programming using the Multiplicative Weights Update Method. 339-348
- Amit Deshpande, Daniel A. Spielman: Improved Smoothed Analysis of the Shadow Vertex Simplex Method. 349-356
- Chaitanya Swamy, David B. Shmoys: Sampling-based Approximation Algorithms for Multi-stage Stochastic. 357-366
- Kedar Dhamdhere, Vineet Goyal, R. Ravi, Mohit Singh: How to Pay, Come What May: Approximation Algorithms for Demand-Robust Covering Problems. 367-378
Session 9
- Henry Cohn, Robert D. Kleinberg, Balázs Szegedy, Christopher Umans: Group-theoretic Algorithms for Matrix Multiplication. 379-388
- Raphael Yuster, Uri Zwick: Answering distance queries in directed graphs using fast matrix multiplication. 389-396
- Avi Wigderson, David Xiao: A Randomness-Efficient Sampler for Matrix-valued Functions and Applications. 397-406
Session 10
- Noga Alon, Asaf Shapira: A Characterization of the (natural) Graph Properties Testable with One-Sided Error. 429-438
- Penny E. Haxell, Brendan Nagle, Vojtech Rödl: An Algorithmic Version of the Hypergraph Regularity Method. 439-448
Session 11
- Ivan Damgård, Serge Fehr, Louis Salvail, Christian Schaffner: Cryptography In the Bounded Quantum-Storage Model. 449-458
- Ran Raz: Quantum Information and the PCP Theorem. 459-468
- 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
- Cristopher Moore, Alexander Russell, Leonard J. Schulman: The Symmetric Group Defies Strong Fourier Sampling. 479-490
Session 12
- Anirban Dasgupta, John E. Hopcroft, Jon M. Kleinberg, Mark Sandler: On Learning Mixtures of Heavy-Tailed Distributions. 491-500
- Jon Feldman, Ryan O'Donnell, Rocco A. Servedio: Learning mixtures of product distributions over discrete domains. 501-510
- Thomas P. Hayes, Alistair Sinclair: A general lower bound for mixing of single-site dynamics on graphs. 511-520
- 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
Session 13
- Boaz Barak, Amit Sahai: How To Play Almost Any Mental Game Over The Net - Concurrent Composition via Super-Polynomial Simulation. 543-552
- Shafi Goldwasser, Yael Tauman Kalai: On the Impossibility of Obfuscation with Auxiliary Input. 553-562
Session 14
- Sergei Izmalkov, Silvio Micali, Matt Lepinski: Rational Secure Computation and Ideal Mechanism Design. 585-595
- Ron Lavi, Chaitanya Swamy: Truthful and Near-Optimal Mechanism Design via Linear Programming. 595-604
- Maria-Florina Balcan, Avrim Blum, Jason D. Hartline, Yishay Mansour: Mechanism Design via Machine Learning. 605-614
Session 15
- Jon M. Kleinberg: An Approximation Algorithm for the Disjoint Paths Problem in Even-Degree Planar Graphs. 627-636
- Erik D. Demaine, Mohammad Taghi Hajiaghayi, Ken-ichi Kawarabayashi: Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring. 637-646
- Philip N. Klein: A linear-time approximation scheme for planar weighted TSP. 647-657
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-19T201401 by the dblp team