default search action
42nd 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 - 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
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
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
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
Testing Random Variables for Independence and Identity. 442-451 - Petros Drineas
Fast Monte-Carlo Algorithms for Approximate Matrix Multiplication. 452-459 - Oded Goldreich
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
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
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
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:
Sp2 subseteq ZPPNP. 620-629
Session 15
- Noga Alon, Alexander Lubotzky
Semi-Direct Product in Groups and Zig-Zag Product in Graphs: Connections and Applications. 630-637 - Amnon Ta-Shma
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
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-13 23:36 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: