![](https://dblp1.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp1.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp1.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp1.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp1.uni-trier.de/img/search.dark.16x16.png)
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
, 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
![](https://dblp1.uni-trier.de/img/cog.dark.24x24.png)
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.