42. FOCS 2001: Las Vegas, Nevada, USA

42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA. IEEE Computer Society, 2001, ISBN 0-7695-1390-5

Tutorials Day

Christos H. Papadimitriou: Game Theory and Mathematical Economics: A Theoretical Computer Scientist's Introduction. 4-8 BibTeX
Piotr Indyk: Algorithmic Applications of Low-Distortion Geometric Embeddings. 10-33 BibTeX
Madhu Sudan: Coding Theory: Tutorial and Survey. 36-53 BibTeX

Session 1

Vladlen Koltun: Almost Tight Upper Bounds for Vertical Decompositions in Four Dimensions. 56-65 BibTeX
Sariel Har-Peled, Kasturi R. Varadarajan: Approximate Shape Fitting via Linearization. 66-73 BibTeX
Pankaj K. Agarwal, Boris Aronov, Micha Sharir: On the Complexity of Many Faces in Arrangements of Circles. 74-83 BibTeX
Sariel Har-Peled: Clustering Motion. 84-93 BibTeX
Sariel Har-Peled: A Replacement for Voronoi Diagrams of Near Linear Size. 94-103 BibTeX

Session 2

Boaz Barak: How to Go Beyond the Black-Box Simulation Barrier. 106-115 BibTeX
Boaz Barak, Oded Goldreich, Shafi Goldwasser, Yehuda Lindell: Resettably-Sound Zero-Knowledge and its Applications. 116-125 BibTeX
Yael Gertner, Tal Malkin, Omer Reingold: On the Impossibility of Basing Trapdoor Functions on Trapdoor Predicates. 126-135 BibTeX
Ran Canetti: Universally Composable Security: A New Paradigm for Cryptographic Protocols. 136-145 BibTeX

Session 3

Anupam Gupta, Amit Kumar, Rajeev Rastogi: Traveling with a Pez Dispenser (Or, Routing Issues in MPLS). 148-157 BibTeX
Baruch Awerbuch, Petra Berenbrink, André Brinkmann, Christian Scheideler: Simple Routing Strategies for Adversarial Systems. 158-167 BibTeX
Matthew Andrews, Antonio Fernández, Ashish Goel, Lisa Zhang: Source Routing and Scheduling in Packet Networks. 168-177 BibTeX
Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg: The Natural Work-Stealing Algorithm is Stable. 178-187 BibTeX

Session 4

Michael Alekhnovich, Alexander A. Razborov: Lower Bounds for Polynomial Calculus: Non-Binomial Case. 190-199 BibTeX
Russell Impagliazzo, Nathan Segerlind: Counting Axioms Do Not Polynomially Simulate Counting Gates. 200-209 BibTeX
Michael Alekhnovich, Alexander A. Razborov: Resolution is Not Automatizable Unless W[P] is Tractable. 210-219 BibTeX
Stefan S. Dantchev, Søren Riis: "Planar" Tautologies Hard for Resolution. 220-229 BibTeX

Session 5

Jittat Fakcharoenphol, Satish Rao: Planar Graphs, Negative Weight Edges, Shortest Paths, Near Linear Time. 232-241 BibTeX
Mikkel Thorup: Compact Oracles for Reachability and Approximate Distances in Planar Digraphs. 242-251 BibTeX
John Hershberger, Subhash Suri: Vickrey Prices and Shortest Paths: What is an Edge Worth?. 252-259 BibTeX
Camil Demetrescu, Giuseppe F. Italiano: Fully Dynamic All Pairs Shortest Paths with Real Edge Weights. 260-267 BibTeX

Session 6

Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, Andrew Chi-Chih Yao: Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity. 270-278 BibTeX
Wim van Dam, Michele Mosca, Umesh V. Vazirani: How Powerful is Adiabatic Quantum Computation?. 279-287 BibTeX
Hartmut Klauck: Lower Bounds for Quantum Communication Complexity. 288-297 BibTeX
Hubert Comon, Guillem Godoy, Robert Nieuwenhuis: The Confluence of Ground Term Rewrite Systems is Decidable in Polynomial Time. 298-307 BibTeX
Jin-yi Cai: On the Average-Case Hardness of CVP. 308-317 BibTeX

Session 7

Joseph Cheriyan, Howard J. Karloff, Yuval Rabani: Approximating Directed Multicuts. 320-328 BibTeX
Martin Pál, Éva Tardos, Tom Wexler: Facility Location with Nonuniform Hard Capacities. 329-338 BibTeX
Lisa Fleischer, Kamal Jain, David P. Williamson: An Iterative Rounding 2-Approximation Algorithm for the Element Connectivity Problem. 339-347 BibTeX
Julia Chuzhoy, Rafail Ostrovsky, Yuval Rabani: Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems. 348-356 BibTeX

Session 8

Amir Shpilka: Lower Bounds for Matrix Product. 358-367 BibTeX
Arne Storjohann: Deterministic Computation of the Frobenius Form. 368-377 BibTeX
Peter Bürgisser: The Complexity of Factors of Multivariate Polynomials. 378-385 BibTeX
Ross M. McConnell: Linear-time Recognition of Circular-arc Graphs. 386-394 BibTeX

Sessoin 9

Yair Bartal, Béla Bollobás, Manor Mendel: A Ramsy-type Theorem for Metric Spaces and its Applications for Metrical Task Systems and Related Problems. 396-405 BibTeX
Adam Meyerson, Kamesh Munagala, Serge A. Plotkin: Designing Networks Incrementally. 406-415 BibTeX
Anupam Gupta, Amit Kumar: Sorting and Selection with Structured Costs. 416-425 BibTeX
Adam Meyerson: Online Facility Location. 426-431 BibTeX

Session 10

Noga Alon: Testing Subgraphs in Large Graphs. 434-441 BibTeX
Tugkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar, Ronitt Rubinfeld, Patrick White: Testing Random Variables for Independence and Identity. 442-451 BibTeX
Petros Drineas, Ravi Kannan: Fast Monte-Carlo Algorithms for Approximate Matrix Multiplication. 452-459 BibTeX
Oded Goldreich, Luca Trevisan: Three Theorems Regarding Testing Graph Properties. 460-469 BibTeX

Session 11

Tim Roughgarden: Designing Networks for Selfish Users is Hard. 472-481 BibTeX
Aaron Archer, Éva Tardos: Truthful Mechanisms for One-Parameter Agents. 482-491 BibTeX
Gopal Pandurangan, Prabhakar Raghavan, Eli Upfal: Building Low-Diameter P2P Networks. 492-499 BibTeX
Dimitris Achlioptas, Amos Fiat, Anna R. Karlin, Frank McSherry: Web Search via Hub Synthesis. 500-509 BibTeX
William Aiello, Fan R. K. Chung, Linyuan Lu: Random Evolution in Massive Graphs. 510-519 BibTeX

Session 12

Stavros G. Kolliopoulos, Neal E. Young: Tight Approximation Results for General Covering Integer Programs. 522-528 BibTeX
Frank McSherry: Spectral Partitioning of Random Graphs. 529-537 BibTeX
Neal E. Young: Sequential and Parallel Algorithms for Mixed Packing and Covering. 538-546 BibTeX
Tibor Szabó, Emo Welzl: Unique Sink Orientations of Cubes. 547-555 BibTeX

Session 13

Tom Bohman, Alan M. Frieze: Arc-Disjoint Paths in Expander Digraphs. 558-567 BibTeX
Claire Kenyon, Elchanan Mossel, Yuval Peres: Glauber Dynamics on Trees and Hyperbolic Graphs. 568-578 BibTeX
Martin E. Dyer, Alan M. Frieze: Randomly Colouring Graphs with Lower Bounds on Girth and Maximum Degree. 579-587 BibTeX
Aravind Srinivasan: Distributions on Level-Sets with Applications to Approximation Algorithms. 588-597 BibTeX

Session 14

Subhash Khot: Improved Inaproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring. 600-609 BibTeX
Johan Håstad, Subhash Khot: Query Efficient PCPs with Perfect Completeness. 610-619 BibTeX
Jin-yi Cai: S^p₂ subseteq ZPP^NP. 620-629 BibTeX

Session 15

Noga Alon, Alexander Lubotzky, Avi Wigderson: Semi-Direct Product in Groups and Zig-Zag Product in Graphs: Connections and Applications. 630-637 BibTeX
Amnon Ta-Shma, David Zuckerman, Shmuel Safra: Extractors from Reed-Muller Codes. 638-647 BibTeX
Ronen Shaltiel, Christopher Umans: Simple Extractors for All Min-Entropies and a New Pseudo-Random Generator. 648-657 BibTeX
Venkatesan Guruswami, Piotr Indyk: Expander-Based Constructions of Efficiently Decodable Codes. 658-667 BibTeX