17. STOC 1985
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, May 6-8, 1985, Providence, Rhode Island, USA. ACM 1985
- Michael Luby:
A Simple Parallel Algorithm for the Maximal Independent Set Problem.
1-10 BibTeX
- Umesh V. Vazirani, Vijay V. Vazirani:
The Two-Processor Scheduling Problem is in R-NC.
11-21 BibTeX
- Richard M. Karp, Eli Upfal, Avi Wigderson:
Constructing a Perfect Matching is in Random NC.
22-32 BibTeX
- Richard Anderson:
A Parallel Algorithm for the Maximal Path Problem.
33-37 BibTeX
- Faith E. Fich, Martin Tompa:
The Parallel Complexity of Exponentiating Polynomials over Finite Fields.
38-47 BibTeX
- Faith E. Fich, Friedhelm Meyer auf der Heide, Prabhakar Ragde, Avi Wigderson:
One, Two, Three \dots Infinity: Lower Bounds for Parallel Computation.
48-58 BibTeX
- Alok Aggarwal:
Tradeoffs for VLSI Models with Subpolynomial Delay.
59-68 BibTeX
- Charles E. Leiserson, F. Miller Maley:
Algorithms for Routing and Testing Routability of Planar VLSI Layouts.
69-78 BibTeX
- Prabhakar Raghavan, Clark D. Thompson:
Provably Good Routing in Graphs: Regular Arrays.
79-87 BibTeX
- Shuji Jimbo, Akira Maruoka:
Expanders Obtained from Affine Transformations (Preliminary Version).
88-97 BibTeX
- Noga Alon:
Expanders, Sorting in Rounds and Superconcentrators of Limited Depth.
98-102 BibTeX
- Robert E. Wilber:
White Pebbles Help.
103-112 BibTeX
- Brenda S. Baker, Steven Fortune, Eric Grosse:
Stable Prehension with Three Fingers.
114-120 BibTeX
- Ming-Deh A. Huang:
Riemann Hypothesis and Finding Roots over Finite Fields.
121-130 BibTeX
- Erich Kaltofen:
Computing with Polynomials Given by Straight-Line Programs I: Greatest Common Divisors.
131-142 BibTeX
- Victor Y. Pan, John H. Reif:
Efficient Parallel Solution of Linear Systems.
143-152 BibTeX
- Katalin Friedl, Lajos Rónyai:
Polynomial Time Solutions of Some Problems in Computational Algebra.
153-162 BibTeX
- Andrew Chi-Chih Yao, F. Frances Yao:
A General Approach to d-Dimensional Geometric Queries (Extended Abstract).
163-168 BibTeX
- Pravin M. Vaidya:
Space-Time Tradeoffs for Orthogonal Range Queries (Extended Abstract).
169-174 BibTeX
- Kenneth L. Clarkson:
A Probabilistic Algorithm for the Post Office Problem.
175-184 BibTeX
- Dov Harel:
A Linear Time Algorithm for Finding Dominators in Flow Graphs and Related Problems.
185-194 BibTeX
- Hitoshi Suzuki, Takao Nishizeki, Nobuji Saito:
Multicommodity Flows in Planar Undirected Graphs and Shortest Paths.
195-204 BibTeX
- Joseph C. Culberson:
The Effect of Updates in Binary Search Trees.
205-212 BibTeX
- Samuel W. Bent, John W. John:
Finding the Median Requires 2n Comparisons.
213-216 BibTeX
- Fan R. K. Chung, D. J. Hajela, Paul D. Seymour:
Self-Organizing Sequential Search and Hilbert's Inequalities.
217-223 BibTeX
- Béla Bollobás, István Simon:
On the Expected Behaviour of Disjoint Set Union Algorithms.
224-231 BibTeX
- David Peleg:
Concurrent Dynamic Logic (Extended Abstract).
232-239 BibTeX
- Moshe Y. Vardi, Larry J. Stockmeyer:
Improved Upper and Lower Bounds for Modal Logics of Programs: Preliminary Report.
240-251 BibTeX
- J. W. de Bakker, John-Jules Ch. Meyer, Ernst-Rüdiger Olderog, Jeffery I. Zucker:
Transition Systems, Infinitary Languages and the Semantics of Uniform Concurrency.
252-262 BibTeX
- Kim B. Bruce, Giuseppe Longo:
Provable Isomorphisms and Domain Equations in Models of Typed Languages (Preliminary Version).
263-272 BibTeX
- Stavros S. Cosmadakis, Paris C. Kanellakis:
Equational Theories and Database Constraints.
273-284 BibTeX
- Samuel R. Buss:
The Polynomial Hierarchy and Fragments of Bounded Arithmetic (Extended Abstract).
285-290 BibTeX
- Shafi Goldwasser, Silvio Micali, Charles Rackoff:
The Knowledge Complexity of Interactive Proof-Systems (Extended Abstract).
291-304 BibTeX
- Ronald Fagin, Moshe Y. Vardi:
An Internal Semantics for Modal Logic: Preliminary Report.
305-315 BibTeX
- Gabriel Bracha:
An O(\mathop lg n) Expected Rounds Randomized Byzantine Generals Protocol.
316-326 BibTeX
- Paul Feldman:
Fault Tolerance of Minimal Path Routings in a Network.
327-334 BibTeX
- Brian A. Coan, Danny Dolev, Cynthia Dwork, Larry J. Stockmeyer:
The Distributed Firing Squad Problem (Preliminary Version).
335-345 BibTeX
- Joseph Y. Halpern, Nimrod Megiddo, Ashfaq A. Munshi:
Optimal Precision in the Presence of Uncertainty (Preliminary Version).
346-355 BibTeX
- Johan Håstad, Adi Shamir:
The Cryptographic Security of Truncated Linearly Related Variables.
356-362 BibTeX
- Leonid A. Levin:
One-Way Functions and Pseudorandom Generators.
363-365 BibTeX
- Umesh V. Vazirani:
Towards a Strong Communication Complexity Theory or Generating Quasi-Random Sequences from Two Communicating Slightly-random Sources (Extended Abstract).
366-378 BibTeX
- Jonathan Goodman, Albert G. Greenberg, Neal Madras, Peter March:
On the Stability of the Ethernet.
379-387 BibTeX
- Péter Gács, John H. Reif:
A Simple Three-Dimensional Real-Time Reliable Cellular Array.
388-395 BibTeX
- Anna Lubiw:
Doubly Lexical Orderings of Matrices.
396-404 BibTeX
- Dung T. Huynh:
The Complexity of the Equivalence Problem for Commutative Semigroups and Symmetric Vector Addition Systems.
405-412 BibTeX
- Friedhelm Meyer auf der Heide:
Fast Algorithms for N-Dimensional Restrictions of Hard Problems.
413-420 BibTeX
- László Babai:
Trading Group Theory for Randomness.
421-429 BibTeX
- Béla Bollobás, Trevor I. Fenner, Alan M. Frieze:
An Algorithm for Finding Hamilton Cycles in a Random Graph.
430-439 BibTeX
- Andrew V. Goldberg, Michael Sipser:
Compression and Ranking.
440-448 BibTeX
- Larry Carter, Larry J. Stockmeyer, Mark N. Wegman:
The Complexity of Backtrack Searches (Preliminary Version).
449-457 BibTeX
- Leslie G. Valiant, Vijay V. Vazirani:
NP Is as Easy as Detecting Unique Solutions.
458-463 BibTeX
- Ron Aharoni, Paul Erdös, Nathan Linial:
Dual Integer Linear Programs and the Relationship between their Optima.
476-483 BibTeX
Copyright © Sat May 16 23:43:10 2009
by Michael Ley (ley@uni-trier.de)
