default search action
26th 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
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
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
Pseudorandomness for network algorithms. 356-364 - Robert P. Kurshan:
The complexity of verification. 365-371 - Yishay Mansour, Noam Nisan
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
An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane. 432-438 - Magnús M. Halldórsson
Greed is good: approximating independent sets in sparse and bounded-degree graphs. 439-448 - Hans L. Bodlaender
Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy. 449-458 - Sanjeev Arora, Yuval Rabani
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
How to share a function securely. 522-533 - Oded Goldreich
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
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
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-17 21: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: