17. STOC 1985: Providence, Rhode Island, USA
Robert Sedgewick (Ed.):
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

- Richard M. Karp, Eli Upfal, Avi Wigderson:
Are Search and Decision Problems Computationally Equivalent?
464-475

- Ron Aharoni, Paul Erdös, Nathan Linial:
Dual Integer Linear Programs and the Relationship between their Optima.
476-483

Last update Sat May 18 19:50:29 2013
CET by the DBLP Team —
Data released under the ODC-BY 1.0 license — See also our legal information page