16. STOC 1984: Washington, DC, USA

• Sergiu Hart, Micha Sharir:
  Probabilistic Temporal Logics for Finite and Bounded Models. 1-13
  
• E. Allen Emerson, A. Prasad Sistla:
  Deciding Branching Time Logic. 14-24
  
• Matthew Hennessy:
  Modelling Fair Processes. 25-30
  
• Pierpaolo Degano, Ugo Montanari:
  Liveness Properties as Convergence in Metric Spaces. 31-38
  
• Rob Gerth:
  Transition Logic: How to Reason About Temporal Properties in a Compositional Way. 39-50
  
• Howard Barringer, Ruurd Kuiper, Amir Pnueli:
  Now You May Compose Temporal Logic Specifications. 51-63
  
• Gianfranco Bilardi, Franco P. Preparata:
  A Minimum Area VLSI Network for O(log n) Time Sorting. 64-70
  
• Frank Thomson Leighton:
  Tight Bounds on the Complexity of Parallel Sorting. 71-80
  
• Pavol Duris, Zvi Galil, Georg Schnitger:
  Lower Bounds on Communication Complexity. 81-91
  
• Norbert Blum:
  An Area-Maximum Edge Length Tradeoff for VLSI Layout. 92-97
  
• Jonathan F. Buss, Peter W. Shor:
  On the Pagenumber of Planar Graphs. 98-100
  
• Andranik Mirzaian:
  Channel Routing in VLSI (Extended Abstract). 101-107
  
• Mark J. Post:
  Minimum Spanning Ellipsoids. 108-116
  
• Chul E. Kim, Timothy A. Anderson:
  Digital Disks and a Digital Compactness Measure. 117-124
  
• Bernard Chazelle:
  Intersecting Is Easier than Sorting. 125-134
  
• Harold N. Gabow, Jon Louis Bentley, Robert Endre Tarjan:
  Scaling and Related Techniques for Geometry Problems. 135-143
  
• Micha Sharir, Amir Schorr:
  On Shortest Paths in Polyhedral Spaces. 144-153
  
• Richard Cole, Micha Sharir, Chee-Keng Yap:
  On k-hulls and Related Problems. 154-166
  
• Deborah S. Franzblau, Daniel J. Kleitman:
  An Algorithm for Constructing Regions with Rectangles: Independence and Minimum Generating Sets for Collections of Intervals. 167-174
  
• Ming-Deh A. Huang:
  Factorization of Polynomials over Finite Fields and Factorization of Primes in Algebraic Number Fields. 175-182
  
• Eric Bach, Gary L. Miller, Jeffrey Shallit:
  Sums of Divisors, Perfect Numbers, and Factoring (Extended Abstract). 183-190
  
• Ravindran Kannan, Arjen K. Lenstra, László Lovász:
  Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers. 191-200
  
• Don Coppersmith:
  Evaluating Logarithms in GF(2^n). 201-207
  
• H. Ong, Claus-Peter Schnorr, Adi Shamir:
  An Efficient Signature Scheme Based on Quadratic Equations. 208-216
  
• Alon Orlitsky, Abbas El Gamal:
  Communication with Secrecy Constraints. 217-224
  
• Danny Dolev, David Maier, Harry G. Mairson, Jeffrey D. Ullman:
  Correcting Faults in Write-Once Memory. 225-229
  
• Uzi Vishkin:
  Randomized Speed-Ups in Parallel Computation. 230-239
  
• Zvi Galil:
  Optimal Parallel Algorithms for String Matching. 240-248
  
• Baruch Awerbuch, Amos Israeli, Yossi Shiloach:
  Finding Euler Circuits in Logarithmic Parallel Time. 249-257
  
• Eli Upfal:
  A Probabilistic Relation between Desirable and Feasible Models of Parallel Computation (A Preliminary Version). 258-265
  
• Richard M. Karp, Avi Wigderson:
  A Fast Parallel Algorithm for the Maximal Independent Set Problem. 266-272
  
• Udi Manber:
  On Maintaining Dynamic Information in a Concurrent Environment (Preliminary Version). 273-278
  
• Jon Louis Bentley, David S. Johnson, Frank Thomson Leighton, Catherine C. McGeoch, Lyle A. McGeoch:
  Some Unexpected Expected Behavior Results for Bin Packing. 279-288
  
• Richard M. Karp, Michael Luby, Alberto Marchetti-Spaccamela:
  A Probabilistic Analysis of Multidimensional Bin Packing Problems. 289-298
  
• Jeff Kahn, Michael E. Saks:
  Every Poset Has a Good Comparison. 299-301
  
• Narendra Karmarkar:
  A New Polynomial-Time Algorithm for Linear Programming. 302-311
  
• Ilan Adler, Nimrod Megiddo:
  A Simplex Algorithm Whose Average Number of Steps is Bounded between Two Quadratic Functions of the Smaller Dimension. 312-323
  
• Dorit S. Hochbaum, David B. Shmoys:
  Powers of Graphs: A Powerful Approximation Technique for Bottleneck Problems. 324-333
  
• Gaston H. Gonnet:
  Determining Equivalence of Expressions in Random Polynomial Time (Extended Abstract). 334-341
  
• Kenneth L. Clarkson:
  Fast Expected-Time and Approximation Algorithms for Geometric Minimum Spanning Trees (Extended Abstract). 342-348
  
• Anselm Blumer, J. Blumer, Andrzej Ehrenfeucht, David Haussler, Ross M. McConnell:
  Building a Complete Inverted File for a Set of Text Files in Linear Time. 349-358
  
• Andrew V. Goldberg, Alberto Marchetti-Spaccamela:
  On Finding the Exact Solution of a Zero-One Knapsack Problem. 359-368
  
• Walter Cunto, J. Ian Munro:
  Average Case Selection. 369-375
  
• Gary L. Miller:
  Finding Small Simple Cycle Separators for 2-Connected Planar Graphs. 376-382
  
• Greg N. Frederickson, Mandayam A. Srinivas:
  Data Structures for On-Line Updating of Matroid Intersection Solutions (Preliminary Version). 383-390
  
• Cees F. Slot, Peter van Emde Boas:
  On Tape Versus Core; An Application of Space Efficient Perfect Hash Functions to the Invariance of Space. 391-400
  
• Wolfgang Maass:
  Quadratic Lower Bounds for Deterministic and Nondeterministic One-Tape Turing Machines (Extended Abstract). 401-408
  
• Michel de Rougemont:
  Uniform Definability on Finite Structures with Successor. 409-417
  
• David Harel:
  A General Result on Infinite Trees and Its Applications (Preliminary Report). 418-427
  
• Dexter Kozen:
  Pebblings, Edgings, and Equational Logic. 428-435
  
• Leslie G. Valiant:
  A Theory of the Learnable. 436-445
  
• Moshe Y. Vardi, Pierre Wolper:
  Automata Theoretic Techniques for Modal Logics of Programs (Extended Abstract). 446-456
  
• Michael Ben-Or, Dexter Kozen, John H. Reif:
  The Complexity of Elementary Algebra and Geometry (Preliminary Abstract). 457-464
  
• Leonid A. Levin:
  Problems, Complete in ``Average'' Instance. 465
  
• Helmut Alt:
  Comparison of Arithmetic Functions with Respect to Boolean Circuit Depth (Extended Abstract). 466-470
  
• Miklós Ajtai, Michael Ben-Or:
  A Theorem on Probabilistic Constant Depth Computations. 471-474
  
• Ravi B. Boppana:
  Threshold Functions and Bounded Depth Monotone Circuits. 475-479
  
• Maria M. Klawe, Wolfgang J. Paul, Nicholas Pippenger, Mihalis Yannakakis:
  On Monotone Formulae with Restricted Depth (Preliminary Version). 480-487
  
• Daniel Dominic Sleator, Robert Endre Tarjan:
  Amortized Efficiency of List Update Rules. 488-492
  
• Greg N. Frederickson, Nancy A. Lynch:
  The Impact of Synchronous Communication on the Problem of Electing a Leader in a Ring. 493-503
  
• Danny Dolev, Joseph Y. Halpern, H. Raymond Strong:
  On the Possibility and Impossibility of Achieving Clock Synchronization. 504-511
  
• Dan E. Willard:
  Log-Logarithmic Protocols for Resolving Ethernet and Semaphore Conflicts (Preliminary Report). 512-521
  
• Baruch Awerbuch:
  An Efficient Network Synchronization Protocol. 522-525
  
• Danny Dolev, Joseph Y. Halpern, Barbara Simons, H. Raymond Strong:
  A New Look at Fault Tolerant Network Routing. 526-535
  
• Andrei Z. Broder, Danny Dolev, Michael J. Fischer, Barbara Simons:
  Efficient Fault Tolerant Routings in Networks. 536-541
  
• Paul M. B. Vitányi:
  Distributed Elections in an Archimedean Ring of Processors (Preliminary Version). 542-547
  

Last update Fri May 25 08:42:10 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page