Volume 17, Number 1, February 1988
Volume 17, Number 2, April 1988
- Eric Bach:
How to Generate Factored Random Numbers.
179-193
- Werner Alexi, Benny Chor, Oded Goldreich, Claus-Peter Schnorr:
RSA and Rabin Functions: Certain Parts are as Hard as the Whole.
194-209
- Charles H. Bennett, Gilles Brassard, Jean-Marc Robert:
Privacy Amplification by Public Discussion.
210-229
- Benny Chor, Oded Goldreich:
Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity.
230-261
- Alan M. Frieze, Johan Håstad, Ravi Kannan, J. C. Lagarias, Adi Shamir:
Reconstructing Truncated Integer Variables Satisfying Linear Congruences.
262-280
- Shafi Goldwasser, Silvio Micali, Ronald L. Rivest:
A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks.
281-308
- Joachim Grollmann, Alan L. Selman:
Complexity Measures for Public-Key Cryptosystems.
309-335
- Johan Håstad:
Solving Simultaneous Modular Equations of Low Degree.
336-341
- J. C. Lagarias, James A. Reeds:
Unique Extrapolation of Polynomial Recurrences.
342-362
- Douglas L. Long, Avi Wigderson:
The Discrete Logarithm Hides O(log n) Bits.
363-372
- Michael Luby, Charles Rackoff:
How to Construct Pseudorandom Permutations from Pseudorandom Functions.
373-386
- Carl Pomerance, Jeffrey W. Smith, Randy Tuler:
A Pipeline Architecture for Factoring Large Integers with the Quadratic Sieve Algorithm.
387-403
- John H. Reif, J. D. Tygar:
Efficient Parallel Pseudorandom Number Generation.
404-411
- Silvio Micali, Charles Rackoff, Bob Sloan:
The Notion of Security for Probabilistic Cryptosystems.
412-426
Volume 17, Number 3, June 1988
- Bernard Chazelle:
A Functional Approach to Data Structures and Its Use in Multidimensional Searching.
427-462
- Philip N. Klein, John H. Reif:
Parallel Time O(log n) Acceptance of Deterministic CFLs on an Exclusive-Write P-RAM.
463-485
- Xin He, Yaacov Yesha:
A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs.
486-491
- Boris Pittel, Jenn-Hwa Yu:
On Search Times for Early-Insertion Coalesced Hashing.
492-503
- Ronald V. Book, Pekka Orponen, David A. Russo, Osamu Watanabe:
Lowness Properties of Sets in the Exponential-Time Hierarchy.
504-516
- Andrew Chi-Chih Yao:
Monotone Bipartite Graph Properties are Evasive.
517-520
- Alessandro D'Atri, Marina Moscarini:
Distance-Hereditary Graphs, Steiner Trees, and Connected Domination.
521-538
- Dorit S. Hochbaum, David B. Shmoys:
A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach.
539-551
- Dan Gusfield:
A Graph Theoretic Approach to Statistical Data Security.
552-571
- Pravin M. Vaidya:
Minimum Spanning Trees in k-Dimensional Space.
572-582
- Alan Siegel, Danny Dolev:
Some Geometry for General River Routing.
583-605
- Faith E. Fich, Prabhakar Ragde, Avi Wigderson:
Relations Between Concurrent-Write Models of Parallel Computation.
606-627
- Timothy J. Long:
Erratum: On Restricting the Size of Oracles Compared with Restricting Access to Oracles.
628 ,
see SIAM J. Comput. 14(3): 585-597(1985)
Volume 17, Number 4, August 1988
- Nachum Dershowitz, Leo Marcus, Andrzej Tarlecki:
Existence, Uniqueness, and Construction of Rewrite Systems.
629-639
- John W. John:
A New Lower Bound for the Set-Partitioning Problem.
640-647
- Robert Schaback:
On the Expected Sublinearity of the Boyer-Moore Algorithm.
648-658
- Paul M. B. Vitányi:
Locality, Communication, and Interconnect Length in Multicomputers.
659-672
- Ludek Kucera, Vera Trnková:
Isomorphism Testing of Unary Algebras.
673-686
- Gary L. Miller, Vijaya Ramachandran, Erich Kaltofen:
Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits.
687-695
- S. S. Ravi, Errol L. Lloyd:
The Complexity of Near-Optimal Programmable Logic Array Folding.
696-710
- Cynthia Dwork, Paris C. Kanellakis, Larry J. Stockmeyer:
Parallel Algorithms for Term Matching.
711-731
- David Avis, C. W. Lai:
The Probabilistic Analysis of a Heuristic for the Assignment Problem.
732-741
- Dan Gusfield:
The Structure of the Stable Roommate Problem: Efficient Representation and Enumeration of All Stable Assignments.
742-769
- Richard Cole:
Parallel Merge Sort.
770-785
- Etienne Grandjean:
A Natural NP-Complete Problem with a Nontrivial Lower Nound.
786-809
- Harold N. Gabow:
Scheduling UET Systems on Two Uniform Processors and Length Two Pipelines.
810-829
- Kenneth L. Clarkson:
A Randomized Algorithm for Closest-Point Queries.
830-847
Volume 17, Number 5, October 1988
- Mikhail J. Atallah, S. Rao Kosaraju:
Efficient Solutions to Some Transportation Problems with Applications to Minimizing Robot Arm Travel.
849-869
- Herbert Edelsbrunner, Steven Skiena:
Probing Convex Polygons with X-Rays.
870-882
- Richard M. Karp, Rajeev Motwani, Prabhakar Raghavan:
Deferred Data Structuring.
883-902
- Ronald V. Book, Ker-I Ko:
On Sets Truth-Table Reducible to Sparse Sets.
903-919
- J. Scott Provan:
An Approximation Scheme for Finding Steiner Trees with Obstacles.
920-934
- Neil Immerman:
Nondeterministic Space is Closed Under Complementation.
935-938
- Stephen L. Bloom, Zoltán Ésik:
Varieties of Iteration Theories.
939-966
- Martin E. Dyer, Alan M. Frieze:
On the Complexity of Computing the Volume of a Polyhedron.
967-974
- Cynthia Dwork, David Peleg, Nicholas Pippenger, Eli Upfal:
Fault Tolerance in Networks of Bounded Degree.
975-988
- Alan L. Selman:
Natural Self-Reducible Sets.
989-996
- Matthew Hennessy:
Axiomatising Finite Concurrent Processes.
997-1017
- Zevi Miller:
A Linear Algorithm for Topological Bandwidth in Degree-Three Trees.
1018-1035
- Paolo Zellini:
Optimal Bounds for Solving Tridiagonal Systems with Preconditioning.
1036-1043
- Colin McDiarmid:
Average-Case Lower Bounds for Searching.
1044-1060
- Robert Endre Tarjan, Christopher J. Van Wyk:
Erratum: An O(n log log n)-Time Algorithm for Triangulating a Simple Polygon.
1061
Volume 17, Number 6, December 1988
- Thomas Lengauer, Egon Wanke:
Efficient Solution of Connectivity Problems on Hierarchically Defined Graphs.
1063-1080
- Michael Ben-Or, Ephraim Feig, Dexter Kozen, Prasoon Tiwari:
A Fast Parallel Algorithm for Determining all Roots of a Polynomial with Real Roots.
1081-1092
- Kurt Mehlhorn, Stefan Näher, Helmut Alt:
A Lower Bound on the Complexity of the Union-Split-Find Problem.
1093-1102
- Robert J. T. Morris, Wing Shing Wong:
A Short-Term Neural Network Memory.
1103-1118
- Béla Bollobás, Graham Brightwell:
Transitive Orientations of Graphs.
1119-1133
- Jan A. Bergstra, Jan Willem Klop, Ernst-Rüdiger Olderog:
Readies and Failures in the Algebra of Communicating Processes.
1134-1177
- Noga Alon, Yossi Azar:
The Average Complexity of Deterministic and Randomized Parallel Comparison-Sorting Algorithms.
1178-1192
- Eric Allender, Roy S. Rubinstein:
P-Printable Sets.
1193-1202
- William J. Knight:
Search in an Ordered Array Having Variable Probe Cost.
1203-1214
- T. Yung Kong, David M. Mount, A. W. Roscoe:
The Decomposition of a Rectangle into Rectangles of Minimal Perimeter.
1215-1231
- Jin-yi Cai, Thomas Gundermann, Juris Hartmanis, Lane A. Hemachandra, Vivian Sewelson, Klaus W. Wagner, Gerd Wechsung:
The Boolean Hierarchy I: Structural Properties.
1232-1252
- Baruch Schieber, Uzi Vishkin:
On Finding Lowest Common Ancestors: Simplification and Parallelization.
1253-1262
- Jim Kadin:
The Polynomial Time Hierarchy Collapses if the Boolean Hierarchy Collapses.
1263-1282 ,
Erratum: SIAM J. Comput. 20(2): 404(1991)
Copyright © Mon Nov 2 21:51:46 2009
by Michael Ley (ley@uni-trier.de)
