default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID40th FOCS 1999: New York, NY, USA
- 40th Annual Symposium on Foundations of Computer Science, FOCS 1999, New York, NY, USA, October 17-18, 1999. IEEE Computer Society 1999, ISBN 0-7695-0409-4
Session 1
- Kamal Jain, Vijay V. Vazirani:
Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems. 2-13 - Jon M. Kleinberg, Éva Tardos:
Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields. 14-23 - Lisa Fleischer:
Approximating Fractional Multicommodity Flow Independent of the Number of Commodities. 24-31 - Foto N. Afrati, Evripidis Bampis, Chandra Chekuri, David R. Karger, Claire Kenyon, Sanjeev Khanna, Ioannis Milis, Maurice Queyranne, Martin Skutella, Clifford Stein, Maxim Sviridenko:
Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates. 32-44
Session 2
- Markus Bläser:
A 5/2 n2-Lower Bound for the Rank of n×n Matrix Multiplication over Arbitrary Fields. 45-50 - Eric Vigoda:
Improved Bounds for Sampling Colorings. 51-59 - Miklós Ajtai:
A Non-linear Time Lower Bound for Boolean Branching Programs. 60-70 - Peter Bro Miltersen, N. V. Vinodchandran:
Derandomizing Arthur-Merlin Games Using Hitting Sets. 71-80 - Valerie King:
Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs. 81-91
Session 3
- Timothy M. Chan:
Dynamic Planar Convex Hull Operations in Near-Logarithmic Amortized Time. 92-99 - Sariel Har-Peled
:
Taking a Walk in a Planar Arrangement. 100-111
Session 4
- John Watrous:
PSPACE Has Constant-Round Quantum Interactive Proof Systems. 112-119 - Silvio Micali, Michael O. Rabin, Salil P. Vadhan:
Verifiable Random Functions. 120-130 - Berthold Vöcking:
How Asymmetry Helps Load Balancing. 131-141 - Uriel Feige:
Noncryptographic Selection Protocols. 142-153
Session 5A
- Piotr Indyk:
A Sublinear Time Approximation Scheme for Clustering in Metric Spaces. 154-159 - Arnon Amir, Alon Efrat, Piotr Indyk, Hanan Samet:
Efficient Regular Data Structures and Algorithms for Location and Proximity Problems. 160-170 - Martin Farach-Colton, Piotr Indyk:
Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via Embeddings. 171-180
Session 5B
- Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson:
Near-Optimal Conversion of Hardness into Pseudo-Randomness. 181-190 - Ran Raz, Omer Reingold, Salil P. Vadhan:
Error Reduction for Extractors. 191-201 - Manindra Agrawal, Somenath Biswas:
Primality and Identity Testing via Chinese Remaindering. 202-209
Session 6A
- Martin E. Dyer, Alan M. Frieze, Mark Jerrum:
On Counting Independent Sets in Sparse Graphs. 210-217 - Christian Borgs, Jennifer T. Chayes, Alan M. Frieze, Jeong Han Kim, Prasad Tetali, Eric Vigoda, Van H. Vu:
Torpid Mixing of Some Monte Carlo Markov Chain Algorithms in Statistical Physics. 218-229 - Ben Morris, Alistair Sinclair:
Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions. 230-240 - V. S. Anil Kumar, H. Ramesh:
Markovian Coupling vs. Conductance for the Jerrum-Sinclair Chain. 241-252
Session 6B
- David Peleg, Vitaly Rubinovich:
A Near-Tight Lower Bound on the Time Complexity of Distributed MST Construction. 253-261 - Yehuda Afek, Gideon Stupp, Dan Touitou:
ong-lived Adaptive Collect with Applications. 262-272 - Rakesh D. Barve, Jeffrey Scott Vitter:
A Theoretical Framework for Memory-Adaptive Algorithms. 273-284 - Matteo Frigo, Charles E. Leiserson, Harald Prokop, Sridhar Ramachandran:
Cache-Oblivious Algorithms. 285-298
Session 7A
- Jon Feldman, Matthias Ruhl:
The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals. 299-308 - David Eppstein:
Setting Parameters by Example. 309-318 - Zhi-Zhong Chen, Xin He, Chun-Hsi Huang:
Finding Double Euler Trails of Planar Graphs in Linear Time. 319-329 - Karsten Weihe:
Edge-Disjoint Routing in Plane Switch Graphs in Linear Time. 330-340
Session 7B
- John Watrous:
On Quantum and Classical Space-bounded Processes with Algebraic Transition Amplitudes. 341-351 - Andris Ambainis:
A Better Lower Bound for Quantum Algorithms Searching an Ordered List. 352-357 - Harry Buhrman, Richard Cleve, Ronald de Wolf, Christof Zalka:
Bounds for Small-Error and Zero-Error Quantum Algorithms. 358-368 - Ashwin Nayak:
Optimal Lower Bounds for Quantum Automata and Random Access Codes. 369-377
Session 8A
- Moses Charikar, Sudipto Guha:
Improved Combinatorial Algorithms for the Facility Location and k-Median Problems. 378-388 - Naoki Katoh, Takeshi Tokuyama:
Lovász's Lemma for the Three-Dimensional K-Level of Concave Surfaces and its Applications. 389-398 - Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair:
Cuts, Trees and l1-Embeddings of Graphs. 399-409
Session 8B
- Uwe Schöning:
A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems. 410-414 - Eli Ben-Sasson, Russell Impagliazzo:
Random CNF's are Hard for the Polynomial Calculus. 415-421 - Maria Luisa Bonet, Nicola Galesi:
A Study of Proof Search Algorithms for Resolution and Polynomial Calculus. 422-432
Session 9A
- S. Muthukrishnan, Rajmohan Rajaraman, Anthony Shaheen, Johannes Gehrke:
Online Scheduling to Minimize Average Stretch. 433-442 - Elias Koutsoupias:
Weak Adversaries for the k-Server Problem. 444-449 - Avrim Blum, Carl Burch, Adam Kalai:
Finely-Competitive Paging. 450-458
Session 9B
- Richard J. Lipton, Anastasios Viglas:
On the Complexity of SAT. 459-464 - Christopher Umans:
Hardness of Approximating Sigma2p Minimization Problems. 465-474 - Ilya Dumer, Daniele Micciancio, Madhu Sudan:
Hardness of Approximating the Minimum Distance of a Linear Code. 475-485
Session 10A
- P. Oscar Boykin, Tal Mor, Matthew Pulver, Vwani P. Roychowdhury, Farrokh Vatan:
On Universal and Fault-Tolerant Quantum Computing: A Novel Basis and a New Constructive Proof of Universality for Shor's Basis. 486-494 - Wojciech Plandowski:
Satisfiability of Word Equations with Constants is in PSPACE. 495-500 - Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan:
An Approximate L1-Difference Algorithm for Massive Data Streams. 501-511 - Deborah Goldman, Sorin Istrail, Christos H. Papadimitriou:
Algorithmic Aspects of Protein Structure Similarity. 512-522
Session 10B
- Cynthia Dwork, Moni Naor, Omer Reingold, Larry J. Stockmeyer:
Magic Functions. 523-534 - Jeong Han Kim, Daniel R. Simon, Prasad Tetali:
Limits on the Efficiency of One-Way Permutation-Based Hash Functions. 535-542 - Amit Sahai:
Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security. 543-553 - Tomas Sander, Adam L. Young, Moti Yung:
Non-Interactive CryptoComputing For NC1. 554-567
Session 11A
- Jon M. Kleinberg, Yuval Rabani, Éva Tardos:
Fairness in Routing and Load Balancing. 568-578 - Ashish Goel, Piotr Indyk:
Stochastic Load Balancing and Related Problems. 579-586 - Malwina J. Luczak, Eli Upfal:
Reducing Network Congestion and Blocking Probability Through Balanced Allocation. 587-595 - Roman M. Kolpakov, Gregory Kucherov:
Finding Maximal Repetitions in a Word in Linear Time. 596-604 - Avi Shoshan, Uri Zwick:
All Pairs Shortest Paths in Undirected Graphs with Integer Weights. 605-615
Session 11B
- Rosa I. Arriaga, Santosh S. Vempala:
An Algorithmic Theory of Learning: Robust Concepts and Random Projection. 616-623 - Adam R. Klivans, Rocco A. Servedio:
Boosting and Hard-Core Sets. 624-633 - Sanjoy Dasgupta:
Learning Mixtures of Gaussians. 634-644 - Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy:
Regular Languages Are Testable with a Constant Number of Queries. 645-655 - Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy:
Efficient Testing of Large Graphs. 656-666
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 2025-11-11 23:03 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:
