default search action
31st STOC 1999: Atlanta, Georgia, USA
- Jeffrey Scott Vitter, Lawrence L. Larmore, Frank Thomson Leighton:
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, May 1-4, 1999, Atlanta, Georgia, USA. ACM 1999, ISBN 1-58113-067-8 - Moses Charikar
, Sudipto Guha, Éva Tardos, David B. Shmoys
A Constant-Factor Approximation Algorithm for the k-Median Problem (Extended Abstract). 1-10 - Kevin D. Wayne:
A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow. 11-18 - Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis:
Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems. 19-28 - Irit Dinur
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability. 29-40 - Funda Ergün, Ravi Kumar, Ronitt Rubinfeld:
Fast Approximate PCPs. 41-50 - Marcos A. Kiwi, Frédéric Magniez, Miklos Santha:
Approximate Testing with Relative Error. 51-60 - Uri Zwick
All Pairs Lightest Shortest Paths. 61-69 - Harold N. Gabow, Haim Kaplan, Robert Endre Tarjan:
Unique Maximum Matching Algorithms. 70-78 - Yuval Ishai, Eyal Kushilevitz:
Improved Upper Bounds on Information-Theoretic Private Information Retrieval (Extended Abstract). 79-88 - Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tal Malkin:
One-Way Functions Are Essential for Single-Server Private Information Retrieval. 89-98 - Moses Charikar
On targeting Markov segments. 99-108 - Edith Cohen, Haim Kaplan:
Exploiting Regularities in Web Traffic Patterns for Cache Replacement. 109-118 - Gen-Huey Chen, Ming-Yang Kao, Yuh-Dauh Lyuu, Hsing-Kuo Wong:
Optimal Buy-and-Hold Strategies for Financial Markets with Bounded Daily Returns. 119-128 - Noam Nisan
Algorithmic Mechanism Design (Extended Abstract). 129-140 - Luca Trevisan:
Construction of Extractors Using Pseudo-Random Generators (Extended Abstract). 141-148 - Ran Raz
Extracting all the Randomness and Reducing the Error in Trevisan's Extractors. 149-158 - Ran Raz
On Recycling the Randomness of States in Space Bounded Computation. 159-168 - Giovanni Di Crescenzo, Russell Impagliazzo
Security-Preserving Hardness-Amplification for Any Regular One-Way Function. 169-178 - Jeff Edmonds:
Scheduling in the Dark. 179-188 - Ashish Goel, Monika Rauch Henzinger, Serge A. Plotkin, Éva Tardos:
Scheduling Data Transfers in a Network and the Set Scheduling Problem. 189-197 - Baruch Awerbuch, Yossi Azar, Stefano Leonardi, Oded Regev:
Minimizing the Flow Time Without Migration. 198-205 - David Gamarnik:
Stability of Adaptive and Non-Adaptive Packet Routing Policies in Adversarial Queueing Networks. 206-214 - Christian Scheideler, Berthold Vöcking:
From Static to Dynamic Routing: Efficient Transformations of Store-and-Forward Protocols. 215-224 - Oded Goldreich, Dana Ron, Madhu Sudan:
Chinese Remaindering with Errors. 225-234 - Vadim Olshevsky, Mohammad Amin Shokrollahi:
A Displacement Approach to Efficient Decoding of Algebraic-Geometric Codes. 235-244 - Moni Naor, Benny Pinkas:
Oblivious Transfer and Polynomial Evaluation. 245-254 - Ran Canetti, Rafail Ostrovsky:
Secure Computation with Honest-Looking Parties: What If Nobody Is Truly Honest? (Extended Abstract). 255-264 - Yefim Dinitz, Shlomo Moran, Sergio Rajsbaum:
Bit Complexity of Breaking and Achieving Symmetry in Chains and Rings (Extended Abstract). 265-274 - Fang Chen, László Lovász, Igor Pak:
Lifting Markov Chains to Speed up Mixing. 275-281 - László Lovász, Ravi Kannan:
Faster Mixing via Average Conductance. 282-287 - Leonard J. Schulman, Vijay V. Vazirani:
Majorizing Estimators and the Approximation of #P-Complete Problems. 288-294 - Paul Beame
Optimal Bounds for the Predecessor Problem. 295-304 - Amit Chakrabarti, Bernard Chazelle, Benjamin Gum, Alexey Lvov:
A Lower Bound on the Complexity of Approximate Nearest-Neighbor Searching on the Hamming Cube. 305-311 - Allan Borodin, Rafail Ostrovsky, Yuval Rabani
Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems. 312-321 - Leonard J. Schulman
Molecular Scale Heat Engines and Scalable Quantum Computation. 322-329 - Lisa Hales, Sean Hallgren:
Quantum Fourier Sampling Simplified. 330-338 - Alexander Russell
Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model. 339-347 - Anna Gál, Adi Rosén:
A Theorem on Sensitivity and Applications in Private Computation. 348-357 - Ran Raz
Exponential Separation of Quantum and Classical Communication Complexity. 358-367 - Masami Amano, Kazuo Iwama:
Undecidability on Quantum Finite Automata. 368-375 - Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma
Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata. 376-383 - Ashwin Nayak, Felix Wu:
The Quantum Query Complexity of Approximating the Median and Related Statistics. 384-393 - Klaus Jansen, Roberto Solis-Oba, Maxim Sviridenko:
Makespan Minimization in Job Shops: A Polynomial Time Approximation Scheme. 394-399 - Martin Skutella, Gerhard J. Woeginger:
A PTAS for Minimizing the Weighted Sum of Job Completion Times on Parallel Machines. 400-407 - Klaus Jansen, Lorant Porkolab:
Improved Approximation Schemes for Scheduling Unrelated Parallel Machines. 408-417 - Jianer Chen, Antonio Miranda:
A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling (Extended Abstract). 418-427 - Piotr Indyk:
Sublinear Time Algorithms for Metric Space Problems. 428-434 - Allan Borodin, Rafail Ostrovsky, Yuval Rabani
Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces. 435-444 - V. S. Anil Kumar, H. Ramesh:
Covering Rectilinear Polygons with Axis-Parallel Rectangles. 445-454 - S. Muthukrishnan, Mike Paterson, Süleyman Cenk Sahinalp, Torsten Suel:
Compact Grid Layouts of Multi-Level Networks. 455-463 - Tomás Feder, Pavol Hell, Sulamita Klein, Rajeev Motwani:
Complexity of Graph Partition Problems. 464-472 - Ming Li, Bin Ma, Lusheng Wang:
Finding Similar Regions in Many Strings. 473-482 - Paolo Ferragina, S. Muthukrishnan, Mark de Berg:
Multi-Method Dispatching: A Geometric Approach With Applications to String Matching Problems. 483-491 - Valerie King, Garry Sagert:
A Fully Dynamic Algorithm for Maintaining the Transitive Closure. 492-498 - Stephen Alstrup, Amir M. Ben-Amram, Theis Rauhe:
Worst-Case and Amortised Optimality in Union-Find (Extended Abstract). 499-506 - Victor Y. Pan, Zhao Q. Chen:
The Complexity of the Matrix Eigenproblem. 507-516 - Eli Ben-Sasson, Avi Wigderson:
Short Proofs are Narrow - Resolution Made Simple. 517-526 - J. Maurice Rojas:
On the Complexity of Diophantine Geometry in Low Dimensions (Extended Abstract). 527-536 - Madhu Sudan, Luca Trevisan, Salil P. Vadhan:
Pseudorandom Generators Without the XOR Lemma (Extended Abstract). 537-546 - Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes. 547-556 - Matthew Andrews, Lisa Zhang:
Packet Routing with Arbitrary End-to-End Delay Requirements. 557-565 - Gopal Pandurangan
Static and Dynamic Evaluation of QoS Properties. 566-573 - Sudipto Guha, Anna Moss, Joseph Naor, Baruch Schieber:
Efficient Recovery from Power Outage (Extended Abstract). 574-582 - Uriel Feige:
Nonmonotonic Phenomena in Packet Routing. 583-591 - Marcus Schaefer:
Graph Ramsey Theory and the Polynomial Hierarchy. 592-601 - Stephen Ponzio, Jaikumar Radhakrishnan, Srinivasan Venkatesh:
The Communication Complexity of Pointer Chasing: Applications of Entropy and Sampling. 602-611 - Edith Cohen, Haim Kaplan, Uri Zwick
Connection Caching. 612-621 - Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber:
Approximating the Throughput of Multiple Machines Under Real-Time Scheduling. 622-631 - Miklós Ajtai:
Determinism versus Non-Determinism for Linear Time RAMs (Extended Abstract). 632-641 - Leslie G. Valiant:
Robust Logics. 642-651 - Eugene M. Luks:
Hypergraph Isomorphism and Structural Equivalence of Boolean Functions. 652-658 - Adam R. Klivans, Dieter van Melkebeek:
Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. 659-667 - David R. Karger
Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut. 668-678 - Uri Zwick:
Outward Rotations: A Tool for Rounding Solutions of Semidefinite Programming Relaxations, with Applications to MAX CUT and Other Problems. 679-687 - Sanjeev Arora, George Karakostas
Approximation Schemes for Minimum Latency Problems. 688-693 - Anupam Gupta:
Embedding Tree Metrics Into Low Dimensional Euclidean Spaces. 694-700 - Rocco A. Servedio:
Computational Sample Complexity and Attribute-Efficient Learning. 701-710 - Johannes Blömer, Jean-Pierre Seifert:
On the Complexity of Computing Short Linearly Independent Vectors and Short Bases in a Lattice. 711-720 - Wojciech Plandowski:
Satisfiability of Word Equations with Constants is in NEXPTIME. 721-725 - Jin-yi Cai, Ajay Nerurkar, D. Sivakumar:
Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time. 726-735 - Piotr Indyk:
Inerpolation of Symmetric Functions and a New Type of Combinatorial Design. 736-740 - Michael R. Capalbo, S. Rao Kosaraju:
Small Universal Graphs. 741-749 - Yevgeniy Dodis, Sanjeev Khanna:
Design Networks with Bounded Pairwise Distance. 750-759 - Gilles Schaeffer:
Random Sampling of Large Planar Maps and Convex Polyhedra. 760-769 - Sanjiv Kapoor:
Efficient Computation of Geodesic Shortest Paths. 770-779 - Amir M. Ben-Amram, Holger Petersen:
Backing Up in Singly Linked Lists. 780-786
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-12-12 20:47 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: