default search action
46th 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 - Navin Goyal, Guy Kindler, Michael E. Saks:
Lower Bounds for the Noisy Broadcast Problem. 40-52
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 - Nir Ailon, Moses Charikar
Fitting tree metrics: Hierarchical clustering and Phylogeny. 73-82 - Ittai Abraham, Yair Bartal, T.-H. Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon M. Kleinberg, Ofer Neiman, Aleksandrs Slivkins:
Metric Embeddings with Relaxed Guarantees. 83-100 - Subhash Khot, Assaf Naor:
Nonembeddability theorems via Fourier analysis. 101-112
Session 3 Machtey Award
- Timothy G. Abbott, Daniel Kane, Paul Valiant:
On the Complexity of Two-PlayerWin-Lose Games. 113-122 - Imre Bárány, Santosh S. Vempala, Adrian Vetta:
Nash Equilibria in Random Games. 123-131 - Jon M. Kleinberg, Prabhakar Raghavan:
Query Incentive Networks. 132-141 - Michel X. Goemans, Vahab S. Mirrokni, Adrian Vetta:
Sink Equilibria and Convergence. 142-154
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
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
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
- Chandra Chekuri, Martin Pál:
A Recursive Greedy Algorithm for Walks in Directed Graphs. 245-253 - 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
Error-Correcting Codes for Automatic Control. 309-316 - Tali Kaufman, Simon Litsyn:
Almost Orthogonal Linear Codes are Locally Testable. 317-326 - Michael Navon, Alex Samorodnitsky:
On Delsarte's Linear Programming Bounds for Binary Codes. 327-338
Session 8
- Sanjeev Arora, Elad Hazan
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 - Ariel Gabizon, Ran Raz
Deterministic Extractors for Affine Sources over Large Fields. 407-418
Session 10
- Noga Alon, Asaf Shapira, Benny Sudakov:
Additive Approximation for Edge-Deletion Problems. 419-428 - 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
The Symmetric Group Defies Strong Fourier Sampling. 479-490
Session 12
- Anirban Dasgupta
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
Analysis and Prediction of the Long-Run Behavior of Probabilistic Sequential Programs with Recursion (Extended Abstract). 521-530 - Orna Kupferman, Moshe Y. Vardi:
Safraless Decision Procedures. 531-542
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 - Rafael Pass
Concurrent Non-Malleable Commitments. 563-572 - Moni Naor, Guy N. Rothblum:
The Complexity of Online Memory Checking. 573-584
Session 14
- Sergei Izmalkov, Silvio Micali, Matt Lepinski:
Rational Secure Computation and Ideal Mechanism Design. 585-595 - Ron Lavi
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 - Anna R. Karlin, David Kempe, Tami Tamir:
Beyond VCG: Frugality of Truthful Mechanisms. 615-626
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 - Nikhil Bansal, Andrea Lodi, Maxim Sviridenko:
A Tale of Two Dimensional Bin Packing. 657-666
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-11-22 19:50 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: