Volume 20, Number 1, February 1991
- Dominique Duval:
Absolute Factorization of Polynomials: A Geometric Approach.
1-21
- Uzi Vishkin:
Deterministic Sampling - A New Technique for Fast Pattern Matching.
22-40
- Qian-Ping Gu, Akira Maruoka:
Amplification of Bounded Depth Monotone Read-Once Boolean Formulae.
41-55
- Alejandro A. Schäffer, Mihalis Yannakakis:
Simple Local Search Problems That are Hard to Solve.
56-87
- Ian Parberry, Pei Yuan Yan:
Improved Upper and Lower Time Bounds for Parallel Random Access Machines Without Simultaneous Writes.
88-99
- Jeffrey D. Ullman, Mihalis Yannakakis:
High-Probability Parallel Transitive-Closure Algorithms.
100-125
- Shih Ping Tung:
Complexity of Sentences Over Number Rings.
126-143
- Marek Chrobak, Lawrence L. Larmore:
An Optimal On-Line Algorithm for k-Servers on Trees.
144-148
- Klaus Sutner, Appajosyula Satyanarayana, Charles L. Suffel:
The Complexity of the Residual Node Connectedness Reliability Problem.
149-155
- Edward M. Reingold, Xiaojun Shen:
More Nearly Optimal Algorithms for Unbounded Searching, Part I: The Finite Case.
156-183
- Edward M. Reingold, Xiaojun Shen:
More Nearly Optimal Algorithms for Unbounded Searching, Part II: The Transfinite Case.
184-208
Volume 20,
Number 2,
April 1991
- Egon Balas, Jue Xue:
Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs.
209-221 ,
Addendum: SIAM J. Comput. 21(5): 1000(1992)
- Jirí Matousek:
Approximate Levels in Line Arrangements.
222-227
- Joseph JáJá, Shing-Chong Chang:
Parallel Algorithms for Channel Routing in the Knock-Knee Model.
228-245
- Ronald V. Book:
Some Observations on Separating Complexity Classes.
246-258
- Herbert Edelsbrunner, Weiping Shi:
An O(n log² h) Time Algorithm for the Three-Dimensional Convex Hull Problem.
259-269
- Paul Beame:
A General Sequential Time-Space Tradeoff for Finding Unique Elements.
270-277
- Oscar H. Ibarra, Tao Jiang:
The Power of Alternating One-Reversal Counters and Stacks.
278-290
- Ron M. Roth, Gyora M. Benedek:
Interpolation and Approximation of Sparse Multivariate Polynomials over GF(2).
291-314
- Yishay Mansour, Baruch Schieber, Prasoon Tiwari:
Lower Bounds for Computations with the Floor Operation.
315-327
- B. K. Natarajan:
Probably Approximate Learning of Sets and Functions.
328-351
- Samir Khuller, Baruch Schieber:
Efficient Parallel Algorithms for Testing k-Connectivity and Finding Disjoint s-t Paths in Graphs.
352-375
- Yehuda Afek, Eli Gafni:
Time and Message Bounds for Election in Synchronous and Asynchronous Complete Networks.
376-394
- Peter Gritzmann, Laurent Habsieger, Victor Klee:
Good and Bad Radii of Convex Polygons.
395-403
- Jim Kadin:
Erratum: The Polynomial Time Hierarchy Collapses if the Boolean Hierarchy Collapses.
404 ,
->SIAM J. Comput. 17(6): 1263-1282(1988)
Volume 20,
Number 3,
June 1991
- Odile Marcotte, Subhash Suri:
Fast Matching Algorithms for Points on a Polygon.
405-422
- Ouri Wolfson, Adrian Segall:
The Communication Complexity of Atomic Commitment and of Gossiping.
423-450
- Ulrich Baum, Michael Clausen:
Some Lower and Upper Complexity Bounds for Generalized Fourier Transforms and their Inverses.
451-459
- János Pach, Micha Sharir:
On Vertical Visibility in Arrangements of Segments and the Queue Size in the Bentley-Ottmann Line Sweeping Algorithm.
460-470
- Mitsunori Ogiwara, Osamu Watanabe:
On Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets.
471-483
- Viliam Geffert:
Nondeterministic Computations in Sublogarithmic Space and Space Constructibility.
484-498
- Uri Zwick:
A 4n Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions.
499-505
- Judy Goldsmith, Lane A. Hemachandra, Deborah Joseph, Paul Young:
Near-Testable Sets.
506-523
- Andrew V. Goldberg, Michael Sipser:
Compression and Ranking.
524-536
- Wei Kuan Shih, Jane W.-S. Liu, Jen-Yao Chung:
Algorithms for Scheduling Imprecise Computations with Timing Constraints.
537-552
- Peter Clote, Evangelos Kranakis:
Boolean Functions, Invariance Groups, and Parallel Complexity.
553-590
- Joachim von zur Gathen:
Tests for Permutation Polynomials.
591-602
Volume 20,
Number 4,
August 1991
Volume 20,
Number 5,
October 1991
Volume 20,
Number 6,
December 1991
- Noam Nisan:
CREW PRAMs and Decision Trees.
999-1007
- Zvi Galil, Raffaele Giancarlo:
On the Exact Complexity of String Matching: Lower Bounds.
1008-1020
- Roy S. Rubinstein:
Self-P-Printability and Polynomial Time Turing Equivalence to a Tally Set.
1021-1033
- Mark H. Overmars, Chee-Keng Yap:
New Upper Bounds in Klee's Measure Problem.
1034-1045
- Hillel Gazit:
An Optimal Randomized Parallel Algorithm for Finding Connected Components in a Graph.
1046-1067
- James L. Hafner, Kevin S. McCurley:
Asymptotically Fast Triangularization of Matrices Over Rings.
1068-1083
- Manuel Blum, Alfredo De Santis, Silvio Micali, Giuseppe Persiano:
Noninteractive Zero-Knowledge.
1084-1118
- John V. Franco:
Elimination of Infrequent Variables Improves Average Case Performance of Satisfiability Algorithms.
1119-1127
- Gary L. Miller, John H. Reif:
Parallel Tree Contraction, Part 2: Further Applications.
1128-1147
- Lane A. Hemachandra, Albrecht Hoene:
On Sets with Efficient Implicit Membership Tests.
1148-1156
- Zvi Galil, Oded Margalit:
An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem.
1157-1189
Copyright © Thu Nov 26 19:45:55 2009
by Michael Ley (ley@uni-trier.de)
