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
  

Last update Fri May 25 08:14:15 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page