default search action
SIAM Journal on Computing, Volume 20
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 - Jirí Matousek:
Approximate Levels in Line Arrangements. 222-227 - Joseph F. 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
Volume 20, Number 3, June 1991
- Odile Marcotte, Subhash Suri:
Fast Matching Algorithms for Points on a Polygon. 405-422 - Ouri Wolfson
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
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
- Kurt Mehlhorn, Chee-Keng Yap:
Constructive Whitney-Graustein Theorem: Or How to Untangle Closed Planar Curves. 603-621 - Jianer Chen, Chee-Keng Yap:
Reversal Complexity. 622-638 - Dan Gusfield:
Computing the Strength of a Graph. 639-654 - Andrew Chi-Chih Yao:
Lower Bounds for Algebraic Computation Trees with Integer Inputs. 655-668 - Christophe Reutenauer, Marcel Paul Schützenberger:
Minimization of Rational Word Functions. 669-685 - Erich E. Sutter:
The Fast m-Transform: A Fast Computation of Cross-Correlations with Binary m-Sequences. 686-694 - Martin E. Dyer
On Counting Lattice Points in Polyhedra. 695-707 - Roberto Tamassia, Jeffrey Scott Vitter
Parallel Transitive Closure and Point Location in Planar Structures. 708-725 - Shun-Ping Chung, Keith W. Ross:
On Nonblocking Multirate Interconnection Networks. 726-736 - Michael T. Goodrich:
Intersecting Line Segments in Parallel with an Output-Sensitive Number of Processors. 737-755 - George I. Davida, Bruce E. Litow:
Fast Parallel Arithmetic via Modular Representation. 756-765 - Don Pigozzi:
Equality-Test and If-Then-Else Algebras: Axiomatization and Specification. 766-805
Volume 20, Number 5, October 1991
- Claire Kenyon-Mathieu, Jeffrey Scott Vitter
The Maximum Size of Dynamic Data Structures. 807-823 - Miroslaw Kutylowski:
Time Complexity of Boolean Functions on CREW PRAMs. 824-833 - Mee Yee Chan:
Embedding of Grids into Optimal Hypercubes. 834-864 - Seinosuke Toda:
PP is as Hard as the Polynomial-Time Hierarchy. 865-877 - Nicholas Pippenger:
Selection Networks. 878-887 - Subir Kumar Ghosh, David M. Mount:
An Output-Sensitive Algorithm for Computing Visibility Graphs. 888-910 - Ming Li, Paul M. B. Vitányi:
Learning Simple Concept Under Simple Distributions. 911-935 - Zhi-Quan Luo, John N. Tsitsiklis:
On the Communication Complexity of Solving a Polynomial Equation. 936-950 - Joel Friedman
The Spectra of Infinite Hypertrees. 951-961 - Ker-I Ko:
On the Complexity of Learning Minimum Time-Bounded Turing Machines. 962-986 - Jan-Ming Ho, D. T. Lee, Chia-Hsiang Chang, C. K. Wong:
Minimum Diameter Spanning Trees and Related Problems. 987-997 - Susan Landau:
Erratum: Factoring Polynomials Over Algebraic Number Fields. 998
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
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
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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-12-23 19:18 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: