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