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