SIAM Journal on Computing, Volume 26

Volume 26, Number 1, February 1997

• Laurent Alonso, Edward M. Reingold, René Schott:
  The Average-Case Complexity of Determining the Majority. 1-14
  
• Moshe Dubiner, Uri Zwick:
  Amplification by Read-Once Formulas. 15-38
  
• Maurice Nivat, Andreas Podelski:
  Minimal Ascending and Descending Tree Automata. 39-58
  
• Yenjo Han, Lane A. Hemaspaandra, Thomas Thierauf:
  Threshold Computation and Cryptographic Security. 59-78
  
• Zhengyu Ge, S. Louis Hakimi:
  Disjoint Rooted Spanning Trees with Small Depths in deBruijn and Kautz Graphs. 79-92
  
• Endre Boros, Peter L. Hammer, Toshihide Ibaraki, Kazuhiko Kawakami:
  Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle. 93-109
  
• Avrim Blum, Prabhakar Raghavan, Baruch Schieber:
  Navigating in Unfamiliar Geometric Terrain. 110-137
  
• Martin Beaudry, Pierre McKenzie, Pierre Péladeau, Denis Thérien:
  Finite Moniods: From Word to Circuit Evaluation. 138-152
  
• Louis Mak:
  Parallelism Always Helps. 153-172
  
• Zhen Liu, Eric Sanlaville:
  Stochastic Scheduling with Variable Profile and Precedence Constraints. 173-187
  
• Richard Chang, William I. Gasarch, Carsten Lund:
  On Bounded Queries and Approximation. 188-209
  
• Martin Farach, Mikkel Thorup:
  Sparse Dynamic Programming for Evolutionary-Tree Comparison. 210-230
  
• Ming-Yang Kao:
  Total Protection of Analytic-Invariant Information in Cross-Tabulated Tables. 231-242
  
• Felipe Cucker, Dima Grigoriev:
  On the Power of Real Turing Machines Over Binary Inputs. 243-254
  
• David R. Karger, Rajeev Motwani:
  An NC Algorithm for Minimum Cuts. 255-272
  
• Shlomi Dolev, Amos Israeli, Shlomo Moran:
  Resource Bounds for Self-Stabilizing Message-Driven Protocols. 273-290
  

Volume 26, Number 2, April 1997

• Torben P. Pedersen, Birgit Pfitzmann:
  Fail-Stop Signatures. 291-330
  
• Heike Ripphausen-Lipa, Dorothea Wagner, Karsten Weihe:
  The Vertex-Disjoint Menger Problem in Planar Graphs. 331-349
  
• Alessandro Panconesi, Aravind Srinivasan:
  Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds. 350-368
  
• Anne Condon, Joan Feigenbaum, Carsten Lund, Peter W. Shor:
  Random Debaters and the Hardness of Approximating Stochastic Functions. 369-400
  
• A. Steinberg:
  A Strip-Packing Algorithm with Absolute Performance Bound 2. 401-409
  
• Shang-Hua Teng, F. Frances Yao:
  Approximating Shortest Superstrings. 410-417
  
• Danny Dolev, Nir Shavit:
  Bounded Concurrent Time-Stamping. 418-455
  
• Paul Walton Purdom Jr., G. Neil Haven:
  Probe Order Backtracking. 456-483
  
• Greg N. Frederickson:
  Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees. 484-538
  
• Rajeev Alur, Hagit Attiya, Gadi Taubenfeld:
  Time-Adaptive Algorithms for Synchronization. 539-556
  
• Eric Allender, José L. Balcázar, Neil Immerman:
  A First-Order Isomorphism Theorem. 557-567
  
• Rakesh M. Verma:
  General Techniques for Analyzing Recursive Algorithms with Applications. 568-581
  
• András Sebö:
  Potentials in Undirected Graphs and Planar Multiflows. 582-603
  

Volume 26, Number 3, June 1997

• Pavel Pudlák, Vojtech Rödl, Jiri Sgall:
  Boolean Circuits, Tensor Ranks, and Communication Complexity. 605-633
  
• Lane A. Hemaspaandra, Jörg Rothe:
  Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets. 634-653
  
• Shai Mohaban, Micha Sharir:
  Ray Shooting Amidst Spheres in Three Dimensions and Related Problems. 654-674
  
• Carsten Thomassen:
  On the Complexity of Finding a Minimum Cycle Cover of a Graph. 675-677
  
• Akiyoshi Shioura, Akihisa Tamura, Takeaki Uno:
  An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs. 678-692
  
• Russell Impagliazzo, Ramamohan Paturi, Michael E. Saks:
  Size-Depth Tradeoffs for Threshold Circuits. 693-707
  
• Wolfgang Maass:
  Bounds for the Computational Power and Learning Complexity of Analog Neural Nets. 708-732
  
• Liming Cai, Jianer Chen:
  On the Amount of Nondeterminism and the Power of Verifying. 733-750
  
• Hans-Ulrich Simon:
  Bounds on the Number of Examples Needed for Learning Functions. 751-763
  
• Stefano Varricchio:
  A Pumping Condition for Regular Sets. 764-771
  
• Gurdip Singh:
  Leader Election in Complete Networks. 772-785
  
• Xiaotie Deng, Sanjeev Mahajan:
  The Cost of Derandomization: Computability or Competitiveness. 786-802
  
• Richard Cole, Ramesh Hariharan:
  Tighter Upper Bounds on the Exact Complexity of String Matching. 803-856
  
• Al Borchers, Ding-Zhu Du:
  The k-Steiner Ratio in Graphs. 857-869
  
• R. Chandrasekaran, Bo Chen, Gábor Galambos, P. R. Narayanan, André van Vliet:
  A Note on ``An On-Line Scheduling Heuristic with Better Worst Case Ratio than Graham's List Scheduling''. 870-872
  

Volume 26, Number 4, August 1997

• Pesech Feldman, Silvio Micali:
  An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement. 873-933
  
• James A. Storer, John H. Reif:
  Error-Resilient Optimal Data Compression. 934-949
  
• Maxime Crochemore, Zvi Galil, Leszek Gasieniec, Kunsoo Park, Wojciech Rytter:
  Constant-Time Randomized Parallel String Matching. 950-960
  
• Ganesh Baliga, Sanjay Jain, Arun Sharma:
  Learning from Multiple Sources of Inaccurate Data. 961-990
  
• Michal Walicki, Sigurd Meldal:
  Singular and Plural Nondeterministic Parameters. 991-1005
  
• Guy Louchard, Claire Kenyon, René Schott:
  Data Structures' Maxima. 1006-1042
  
• Stephen A. Fenner, Steven Homer, Mitsunori Ogihara, Alan L. Selman:
  Oracles that Compute Values. 1043-1065
  
• James R. Driscoll, Dennis M. Healy Jr., Daniel N. Rockmore:
  Fast Discrete Polynomial Transforms with Applications to Data Analysis for Distance Transitive Graphs. 1066-1099
  
• Leslie Ann Goldberg, Mark Jerrum, Frank Thomson Leighton, Satish Rao:
  Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel Computers. 1100-1119
  
• Leonidas J. Guibas, Rajeev Motwani, Prabhakar Raghavan:
  The Robot Localization Problem. 1120-1138
  
• Dalit Naor, Dan Gusfield, Charles U. Martel:
  A Fast Algorithm for Optimally Increasing the Edge Connectivity. 1139-1165
  
• Dorit Dor, Michael Tarsi:
  Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture. 1166-1187
  
• Bonnie Berger:
  The Fourth Moment Method. 1188-1207
  
• Phillip B. Gibbons, Ephraim Korach:
  Testing Shared Memories. 1208-1244
  
• Alexander V. Karzanov, S. Thomas McCormick:
  Polynomial Methods for Separable Convex Optimization in Unimodular Linear Spaces with Applications. 1245-1275
  

Volume 26, Number 5, October 1997

• Richard J. Anderson, Heather Woll:
  Algorithms for the Certified Write-All Problem. 1277-1283
  
• Sam M. Kim:
  Computational Modeling for Genetic Splicing Systems. 1284-1309
  
• László Babai, Eugene M. Luks, Ákos Seress:
  Fast Management of Permutation Groups I. 1310-1342
  
• Brenda S. Baker:
  Parameterized Duplication in Strings: Algorithms and an Application to Software Maintenance. 1343-1362
  
• Kazuhisa Makino, Toshihide Ibaraki:
  The Maximum Latency and Identification of Positive Boolean Functions. 1363-1383
  
• Matthew J. Katz, Micha Sharir:
  An Expander-Based Approach to Geometric Optimization. 1384-1408
  
• Umesh V. Vazirani:
  Introduction to Special Section on Quantum Computation. 1409-1410
  
• Ethan Bernstein, Umesh V. Vazirani:
  Quantum Complexity Theory. 1411-1473
  
• Daniel R. Simon:
  On the Power of Quantum Computation. 1474-1483
  
• Peter W. Shor:
  Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. 1484-1509
  
• Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh V. Vazirani:
  Strengths and Weaknesses of Quantum Computing. 1510-1523
  
• Leonard M. Adleman, Jonathan DeMarrais, Ming-Deh A. Huang:
  Quantum Computability. 1524-1540
  
• Adriano Barenco, André Berthiaume, David Deutsch, Artur Ekert, Richard Jozsa, Chiara Macchiavello:
  Stabilization of Quantum Computations by Symmetrization. 1541-1557
  

Volume 26, Number 6, December 1997

• Philip D. MacKenzie:
  The Random Adversary: A Lower-Bound Technique for Randomized Parallel Algorithms. 1559-1580
  
• Richard J. Cole, Bruce M. Maggs, Ramesh K. Sitaraman:
  Reconfiguring Arrays with Faults Part I: Worst-Case Faults. 1581-1611
  
• John Hershberger, Subhash Suri:
  Matrix Searching with the Shortest-Path Metric. 1612-1634
  
• Joseph Cheriyan:
  Randomized Õ(M(|V|)) Algorithms for Problems in Matching Theory. 1635-1669
  
• Amihood Amir, Dmitry Keselman:
  Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms. 1656-1669
  
• Boris Aronov, Micha Sharir, Boaz Tagansky:
  The Union of Convex Polyhedra in Three Dimensions. 1670-1688
  
• Pankaj K. Agarwal, Boris Aronov, Joseph O'Rourke, Catherine A. Schevon:
  Star Unfolding of a Polytope with Applications. 1689-1713
  
• Pankaj K. Agarwal, Boris Aronov, Micha Sharir:
  Computing Envelopes in Four Dimensions with Applications. 1714-1732
  
• Noga Alon, Nabil Kahale:
  A Spectral Technique for Coloring Random 3-Colorable Graphs. 1733-1748
  
• Sampath Kannan, Tandy Warnow:
  A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies. 1749-1763
  
• Jehoshua Bruck, Robert Cypher, Ching-Tien Ho:
  Fault-Tolerant Meshes with Small Degree. 1764-1784
  
• Boris Aronov, Micha Sharir:
  On Translational Motion Planning of a Convex Polyhedron in 3-Space. 1785-1803
  

Last update Sat May 26 07:00:35 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page