26. STOC 1994: Montréal, Québec, Canada

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada. ACM 1994 BibTeX

@proceedings{DBLP:conf/stoc/STOC26,
  title     = {Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory
               of Computing, 23-25 May 1994, Montr{\'e}al, Qu{\'e}bec,
               Canada},
  booktitle = {STOC},
  publisher = {ACM},
  year      = {1994},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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