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