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

@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
  
• 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
  
• 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 Kahale:
  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
  
• 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 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
  
• 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