46. FOCS 2005: Pittsburgh, PA, USA

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 l₁. 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, Hubert T.-H. 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 M. Kane, Paul Valiant:
  On the Complexity of Two-PlayerWin-Lose Games. 113-122
  
• Imre Bárány, Santosh 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, 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

• 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, Leonard J. Schulman:
  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, 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
  
• 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, 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
  
• 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, Alon Rosen:
  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, 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
  
• 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
  

Last update Sun May 19 22:16:31 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page