default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID27th STOC 1995: Las Vegas, NV, USA
- Frank Thomson Leighton, Allan Borodin:
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 29 May-1 June 1995, Las Vegas, Nevada, USA. ACM 1995, ISBN 0-89791-718-9 - Samir Khuller, Balaji Raghavachari:
Improved approximation algorithms for uniform connectivity problems. 1-10 - David R. Karger
:
A randomized fully polynomial time approximation scheme for the all terminal network reliability problem. 11-17 - David R. Karger, Serge A. Plotkin:
Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows. 18-25 - Jon M. Kleinberg, Éva Tardos:
Approximations for the disjoint paths problem in high-diameter planar networks. 26-35 - Matthew K. Franklin, Moti Yung:
Secure hypergraphs: privacy from partial broadcast (Extended Abstract). 36-44 - Mihir Bellare, Oded Goldreich, Shafi Goldwasser:
Incremental cryptography and application to virus protection. 45-56 - Mihir Bellare, Phillip Rogaway:
Provably secure session key distribution: the three party case. 57-66 - Andrew Chi-Chih Yao:
Security of quantum protocols against coherent measurements. 67-75 - László Lovász, Peter Winkler:
Efficient stopping rules for Markov chains. 76-82 - Yuval Rabani, Yuri Rabinovich, Alistair Sinclair:
A computational view of population genetics. 83-92 - Haim Kaplan, Robert Endre Tarjan:
Persistent lists with catenation via recursive slow-down. 93-102 - Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson:
On data structures and asymmetric communication complexity. 103-111 - Persi Diaconis, Laurent Saloff-Coste:
What do we know about the Metropolis algorithm? 112-129 - Stephen Ponzio:
A lower bound for integer multiplication with read-once branching programs. 130-139 - Noam Nisan, Amnon Ta-Shma:
Symmetric logspace is closed under complement. 140-146 - Jeff Edmonds, Chung Keung Poon:
A nearly optimal time-space lower bound for directed st-connectivity on the NNJAG model. 147-156 - William E. Hart, Sorin Istrail:
Fast protein folding in the hydrophobic-hydrophilic model within three-eights of optimal (Extended Abstract). 157-168 - S. Rao Kosaraju, Arthur L. Delcher:
Large-scale assembly of DNA strings and space-efficient construction of suffix trees. 169-177 - Sridhar Hannenhalli, Pavel A. Pevzner:
Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. 178-189 - Lisa Hellerstein, Krishnan Pillaipakkamnatt, Vijay Raghavan, Dawn Wilkins:
How many queries are needed to learn? 190-199 - Marek Karpinski, Angus Macintyre:
Polynomial bounds for VC dimension of sigmoidal neural networks. 200-208 - Jyrki Kivinen, Manfred K. Warmuth:
Additive versus exponentiated gradient updates for linear prediction. 209-218 - Nader H. Bshouty, Christino Tamon:
On the Fourier spectrum of monotone functions (Extended Abstract). 219-228 - Prabhakar Raghavan, Eli Upfal:
Stochastic contention resolution with short delays. 229-237 - Micah Adler, Soumen Chakrabarti, Michael Mitzenmacher, Lars Eilstrup Rasmussen:
Parallel randomized load balancing (Preliminary Version). 238-247 - Mor Harchol-Balter, David Wolfe:
Bounding delays in packet-routing networks. 248-257 - Yishay Mansour, Boaz Patt-Shamir:
Many-to-one packet routing on grids (Extended Abstract). 258-267 - Aravind Srinivasan:
Improved approximations of packing and covering problems. 268-276 - Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh S. Vempala:
Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen. 277-283 - Sanjeev Arora, David R. Karger, Marek Karpinski:
Polynomial time approximation schemes for dense instances of NP-hard problems. 284-293 - Avrim Blum, Prasad Chalasani, Santosh S. Vempala:
A constant-factor approximation for the k-MST problem in the plane. 294-302 - Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi:
The relative complexity of NP search problems. 303-314 - Erich Grädel, Klaus Meer:
Descriptive complexity theory over the real numbers. 315-324 - Jie Wang:
Average-case completeness of a word problem for groups. 325-334 - Felipe Cucker, Marek Karpinski, Pascal Koiran, Thomas Lickteig, Kai Werther:
On real Turing machines that toss coins. 335-342 - Pankaj K. Agarwal, Prabhakar Raghavan, Hisao Tamaki:
Motion planning for a steering-constrained robot through moderate obstacles. 343-352 - Lydia E. Kavraki, Jean-Claude Latombe, Rajeev Motwani, Prabhakar Raghavan:
Randomized query processing in robot path planning (Extended Abstract). 353-362 - Rajeev Alur, Costas Courcoubetis, Mihalis Yannakakis:
Distinguishing tests for nondeterministic and probabilistic machines. 363-372 - Thomas A. Henzinger, Peter W. Kopke, Anuj Puri, Pravin Varaiya:
What's decidable about hybrid automata? 373-382 - William R. Pulleyblank:
Two Steiner tree packing problems (Extended Abstract). 383-387 - Daniel A. Spielman:
Linear-time encodable and decodable error-correcting codes. 388-397 - Erich L. Kaltofen, Victor Shoup:
Subquadratic-time factoring of polynomials over finite fields. 398-406 - Funda Ergün:
Testing multivariate linear functions: overcoming the generator bottleneck. 407-416 - Arne Andersson, Johan Håstad, Ola Petersson:
A tight lower bound for searching a sorted array. 417-426 - Arne Andersson, Torben Hagerup, Stefan Nilsson, Rajeev Raman:
Sorting in linear time? 427-436 - Nabil Kahalé, Frank Thomson Leighton, Yuan Ma, C. Greg Plaxton, Torsten Suel, Endre Szemerédi:
Lower bounds for sorting networks. 437-446 - Ran Raz:
A parallel repetition theorem. 447-456 - Uriel Feige, Joe Kilian:
Impossibility results for recycling random bits in two-prover proof systems. 457-468 - William Aiello, Mihir Bellare, Ramarathnam Venkatesan:
Knowledge on the average-perfect, statistical and logarithmic. 469-478 - Michael E. Saks, Aravind Srinivasan, Shiyu Zhou:
Explicit dispersers with polylog degree. 479-488 - Sunil Arya, Gautam Das, David M. Mount, Jeffrey S. Salowe, Michiel H. M. Smid:
Euclidean spanners: short, thin, and lanky. 489-498 - Zvi Galil, Xiangdong Yu:
Short length versions of Menger's theorem (Extended Abstract). 499-508 - Yefim Dinitz, Zeev Nutov:
A 2-level cactus model for the system of minimum and minimum+1 edge-cuts in a graph and its incremental maintenance. 509-518 - Monika Rauch Henzinger, Valerie King:
Randomized dynamic graph algorithms with polylogarithmic time per operation. 519-527 - Shlomi Dolev, Evangelos Kranakis, Danny Krizanc, David Peleg:
Bubbles: adaptive routing scheme for high-speed dynamic networks (Extended Abstract). 528-537 - Yehuda Afek, Dalia Dauber, Dan Touitou:
Wait-free made fast (Extended Abstract). 538-547 - Bhaskar Ghosh, Frank Thomson Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, Rajmohan Rajaraman, Andréa W. Richa, Robert Endre Tarjan, David Zuckerman:
Tight analyses of two local load balancing algorithms. 548-558 - Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén:
Log-space polynomial end-to-end communication. 559-568 - Mikael Goldmann, Johan Håstad:
Monotone circuits for connectivity have depth (log n)2-o(1) (Extended Abstract). 569-574 - Maria Luisa Bonet, Toniann Pitassi, Ran Raz:
Lower bounds for cutting planes proofs with small coefficients. 575-584 - Robert Beals, Tetsuro Nishino, Keisuke Tanaka:
More on the complexity of negation-limited circuits. 585-595 - Ilan Kremer, Noam Nisan, Dana Ron:
On randomized one-round communication complexity. 596-605 - Ran Canetti, Sandy Irani:
Bounding the power of preemption in randomized scheduling. 606-615 - Amotz Bar-Noy, Ran Canetti, Shay Kutten, Yishay Mansour, Baruch Schieber:
Bandwidth allocation with preemption. 616-625 - Amos Fiat, Anna R. Karlin:
Randomized and multipointer paging with locality of reference. 626-634 - Uriel Feige:
Randomized graph products, chromatic numbers, and Lovasz theta-function. 635-640 - Al Borchers, Ding-Zhu Du:
The k-Steiner ratio in graphs. 641-649 - Thomas Raschle, Klaus Simon:
Recognition of graphs with threshold dimension two. 650-661 - David Eppstein:
Geometric lower bounds for parametric matroid optimization. 662-671 - Nancy M. Amato, Michael T. Goodrich, Edgar A. Ramos:
Computing faces in segment and simplex arrangements (Preliminary Version). 672-682 - Gary L. Miller, Dafna Talmor, Shang-Hua Teng, Noel Walkington:
A Delaunay based numerical method for three dimensions: generation, formulation, and partition. 683-692 - Paolo Ferragina, Roberto Grossi:
A fully-dynamic data structure for external substring search (Extended Abstract). 693-702 - Martin Farach, Mikkel Thorup:
String matching in Lempel-Ziv compressed strings. 703-712 - Artur Czumaj, Zvi Galil, Leszek Gasieniec, Kunsoo Park, Wojciech Plandowski:
Work-time-optimal parallel algorithms for string problems. 713-722 - Noam Nisan, Avi Wigderson:
On the complexity of bilinear forms: dedicated to the memory of Jacques Morgenstern. 723-732 - Bernard Chazelle:
Lower bounds for off-line range searching. 733-740 - Victor Y. Pan:
Optimal (up to polylog factors) sequential and parallel algorithms for approximating complex polynomial zeros. 741-750 - John H. Reif:
Work efficient parallel solution of Toeplitz systems and polynomial GCD. 751-761
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-12-05 22:23 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:
