16. STOC 1984
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1984, Washington, DC, USA. ACM 1984
- 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
Copyright © Tue Dec 8 20:19:56 2009
by Michael Ley (ley@uni-trier.de)
