26. STOC 1994: Montréal, Québec, Canada
Frank Thomson Leighton, Michael T. Goodrich (Eds.): 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- 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 Henzinger, Sairam Subramanian: Faster shortest-path algorithms for planar graphs. 27-37
- 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
- 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
- Baruch Awerbuch, Lenore Cowen, Mark A. Smith: Efficient asynchronous distributed symmetry breaking. 214-223
- 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
- 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. 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 Kahale: A spectral technique for coloring random 3-colorable graphs (preliminary version). 346-355
- 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
- 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 Vorobjov: 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
- 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
- Philippe Jacquet, Wojciech Szpankowski: A functional equation often arising in the analysis of algorithms (extended abstract). 780-789
- Mihir Bellare, Shafi Goldwasser, Carsten Lund, Alexander Russell: Efficient probabilistic checkable proofs and applications to approximation. 820
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-17T203403 by the dblp team