42. FOCS 2001: Las Vegas, Nevada, USA

Tutorials Day

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

Session 1

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

Session 2

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

Session 3

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

Session 4

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

Session 5

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

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
• Wim van Dam, Michele Mosca, Umesh V. Vazirani: How Powerful is Adiabatic Quantum Computation?. 279-287
• Hartmut Klauck: Lower Bounds for Quantum Communication Complexity. 288-297
• Hubert Comon, Guillem Godoy, Robert Nieuwenhuis: The Confluence of Ground Term Rewrite Systems is Decidable in Polynomial Time. 298-307
• Jin-yi Cai: On the Average-Case Hardness of CVP. 308-317

Session 7

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

Session 8

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

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
• Adam Meyerson, Kamesh Munagala, Serge A. Plotkin: Designing Networks Incrementally. 406-415
• Anupam Gupta, Amit Kumar: Sorting and Selection with Structured Costs. 416-425
• Adam Meyerson: Online Facility Location. 426-431

Session 10

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

Session 11

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

Session 12

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

Session 13

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

Session 14

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

Session 15

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