17. STOC 1985: Providence, Rhode Island, USA

• 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