default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID26th STOC 1994: Montréal, Québec, Canada
- Frank Thomson Leighton, Michael T. Goodrich:
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada. ACM 1994, ISBN 0-89791-663-8 - Fan R. K. Chung, Shing-Tung Yau:
A near optimal algorithm for edge separators (preliminary version). 1-8 - Philip N. Klein, Robert Endre Tarjan:
A randomized linear-time algorithm for finding minimum spanning trees. 9-15 - Edith Cohen:
Polylog-time and near-linear work approximation scheme for undirected shortest paths. 16-26 - Philip N. Klein, Satish Rao, Monika Rauch, Sairam Subramanian:
Faster shortest-path algorithms for planar graphs. 27-37 - Keisuke Tanaka, Tetsuro Nishino:
On the complexity of negation-limited Boolean networks. 38-47 - Matthias Krause, Pavel Pudlák:
On the computational power of depth 2 circuits with threshold and modulo gates. 48-57 - Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer
:
Circuit complexity: from the worst case to the average case. 58-67 - Vince Grolmusz:
A weight-size trade-off for circuits with MOD m gates. 68-74 - Bernard Chazelle:
Computational geometry: a retrospective. 75-94 - Marco Pellegrini:
On point location and motion planning among simplices. 95-104 - Mark de Berg, Katrin Dobrindt, Otfried Schwarzkopf:
On lazy randomized incremental construction. 105-114 - Bala Kalyanasundaram, Kirk Pruhs:
Fault-tolerant scheduling. 115-124 - Anna R. Karlin, Greg Nelson, Hisao Tamaki:
On the fault tolerance of the butterfly. 125-133 - Prabhakar Raghavan, Eli Upfal:
Efficient routing in all-optical networks. 134-143 - Eric A. Brewer, Frederic T. Chong, Tom Leighton:
Scalable expanders: exploiting hierarchical random wiring. 144-152 - Philip D. MacKenzie, C. Greg Plaxton, Rajmohan Rajaraman:
On contention resolution protocols and associated probabilistic phenomena. 153-162 - Avrim Blum, Prasad Chalasani, Don Coppersmith, William R. Pulleyblank, Prabhakar Raghavan, Madhu Sudan:
The minimum latency problem. 163-171 - Uriel Feige, Joe Kilian:
Two prover protocols: low error at affordable rates. 172-183 - Mihir Bellare, Madhu Sudan:
Improved non-approximability results. 184-193 - Alexander Polishchuk, Daniel A. Spielman:
Nearly-linear size holographic proofs. 194-203 - Alexander A. Razborov, Steven Rudich:
Natural proofs. 204-213 - Baruch Awerbuch, Lenore Cowen, Mark A. Smith:
Efficient asynchronous distributed symmetry breaking. 214-223 - Jae-Heon Yang, James H. Anderson:
Time bounds for mutual exclusion and related problems. 224-233 - Rafail Ostrovsky, Sridhar Rajagopalan, Umesh V. Vazirani:
Simple and efficient leader election in the full information model. 234-242 - Maurice Herlihy, Nir Shavit:
A simple constructive computability theorem for wait-free computation. 243-252 - Avrim Blum, Merrick L. Furst, Jeffrey C. Jackson, Michael J. Kearns, Yishay Mansour, Steven Rudich:
Weakly learning DNF and characterizing statistical query learning using Fourier analysis. 253-262 - Peter Auer, Philip M. Long:
Simulating access to hidden information while learning. 263-272 - Michael J. Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie:
On the learnability of discrete distributions. 273-282 - Kalvis Apsitis, Rusins Freivalds, Carl H. Smith:
Choosing a learning team: a topological approach. 283-289 - Ramesh Hariharan:
Optimal parallel suffix tree construction. 290-299 - Süleyman Cenk Sahinalp, Uzi Vishkin:
Symmetry breaking for suffix tree construction. 300-309 - S. Rao Kosaraju:
Real-time pattern matching and quasi-real-time construction of suffix trees (preliminary version). 310-316 - Arne Andersson, Torben Hagerup, Johan Håstad, Ola Petersson:
The complexity of searching a sorted array of strings. 317-325 - Noga Alon, Raphael Yuster, Uri Zwick:
Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs. 326-335 - Andrew M. Odlyzko:
Search for the maximum of a random walk. 336-345 - Noga Alon, Nabil Kahalé:
A spectral technique for coloring random 3-colorable graphs (preliminary version). 346-355 - Russell Impagliazzo, Noam Nisan, Avi Wigderson:
Pseudorandomness for network algorithms. 356-364 - Robert P. Kurshan:
The complexity of verification. 365-371 - Yishay Mansour, Noam Nisan, Uzi Vishkin:
Trade-offs between communication throughput and parallel time. 372-381 - Torben Hagerup:
Optimal parallel string algorithms: sorting, merging and computing the minimum. 382-391 - Keju Ma, Joachim von zur Gathen:
The computational complexity of recognizing permutation functions. 392-401 - Samir Khuller, Balaji Raghavachari, Neal E. Young:
Low degree spanning trees of small weight. 412-421 - Michel X. Goemans, David P. Williamson:
.879-approximation algorithms for MAX CUT and MAX 2SAT. 422-431 - Naveen Garg, Dorit S. Hochbaum:
An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane. 432-438 - Magnús M. Halldórsson, Jaikumar Radhakrishnan:
Greed is good: approximating independent sets in sparse and bounded-degree graphs. 439-448 - Hans L. Bodlaender, Michael R. Fellows, Michael T. Hallett:
Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy. 449-458 - Sanjeev Arora, Yuval Rabani, Umesh V. Vazirani:
Simulating quadratic dynamical systems is PSPACE-complete (preliminary version). 459-467 - Madhav V. Marathe, Harry B. Hunt III, Richard Edwin Stearns, Venkatesh Radhakrishnan:
Approximation schemes for PSPACE-complete problems for succinct specifications (preliminary version). 468-477 - Meera Sitharam:
Pseudorandom generators and learning algorithms for AC. 478-486 - Baruch Awerbuch, Tom Leighton:
Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks. 487-496 - Stephen A. Vavasis, Yinyu Ye:
An accelerated interior point method whose running time depends only on A (extended abstract). 512-521 - Alfredo De Santis, Yvo Desmedt, Yair Frankel, Moti Yung:
How to share a function securely. 522-533 - Oded Goldreich, Rafail Ostrovsky, Erez Petrank:
Computational complexity and knowledge complexity (extended abstract). 534-543 - Josh Cohen Benaloh, Dwight Tuinstra:
Receipt-free secret-ballot elections (extended abstract). 544-553 - Uriel Feige, Joe Kilian, Moni Naor:
A minimal model for secure computation (extended abstract). 554-563 - Oded Goldreich, Avi Wigderson:
Tiny families of functions with random properties (preliminary version): a quality-size trade-off for hashing. 574-584 - Suresh Chari, Pankaj Rohatgi, Aravind Srinivasan:
Improved algorithms via approximations of probability distributions (extended abstract). 584-592 - Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Eli Upfal:
Balanced allocations (extended abstract). 593-602 - Ketan Mulmuley:
Lower bounds for parallel linear programming and other problems. 603-614 - Andrew Chi-Chih Yao:
Decision tree complexity and Betti numbers. 615-624 - Peter Bro Miltersen:
Lower bounds for union-split-find related problems on random access machines. 625-634 - Dima Grigoriev, Marek Karpinski, Nicolai N. Vorobjov Jr.:
Lower bounds on testing membership to a polyhedron by algebraic decision trees. 635-644 - Avi Wigderson:
The amazing power of pairwise independence (abstract). 645-647 - David R. Karger:
Random sampling in cut, flow, and network design problems. 648-657 - Tao Jiang, Joel I. Seiferas, Paul M. B. Vitányi:
Two heads are better than two tapes. 668-675 - Anne Condon, Lisa Hellerstein, Samuel Pottle, Avi Wigderson:
On the power of finite automata with both nondeterministic and probabilistic states (preliminary version). 676-685 - Monika Rauch:
Improved data structures for fully dynamic biconnectivity. 686-695 - Harold N. Gabow:
Efficient splitting off algorithms for graphs. 696-705 - Johannes A. La Poutré:
Alpha-algorithms for incremental planarity testing (preliminary version). 706-715 - Yefim Dinitz, Alek Vainshtein:
The connectivity carcass of a vertex subset in a graph and its incremental maintenance. 716-725 - Christos H. Papadimitriou, Mihalis Yannakakis:
On complexity as bounded rationality (extended abstract). 726-733 - Richard J. Lipton, Neal E. Young:
Simple strategies for large zero-sum games with applications to complexity theory. 734-740 - Lance Fortnow, Duke Whang:
Optimality and domination in repeated games with bounded players. 741-749 - Daphne Koller, Nimrod Megiddo, Bernhard von Stengel:
Fast algorithms for finding randomized strategies in game trees. 750-759 - Tao Jiang, Eugene L. Lawler, Lusheng Wang:
Aligning sequences via an evolutionary tree: complexity and approximation. 760-769 - S. Muthukrishnan, Krishna V. Palem:
Non-standard stringology: algorithms and complexity. 770-779 - Philippe Jacquet, Wojciech Szpankowski:
A functional equation often arising in the analysis of algorithms (extended abstract). 780-789 - Sridhar Rajagopalan, Leonard J. Schulman:
A coding theorem for distributed computation. 790-799 - Rajeev Alur, Hagit Attiya, Gadi Taubenfeld:
Time-adaptive algorithms for synchronization. 800-809 - Boaz Patt-Shamir, Sergio Rajsbaum:
A theory of clock synchronization (extended abstract). 810-819 - Mihir Bellare, Shafi Goldwasser, Carsten Lund, Alexander Russell:
Efficient probabilistic checkable proofs and applications to approximation. 820
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-03 20:31 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:
