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
Copyright © Tue Nov 24 00:01:51 2009
by Michael Ley (ley@uni-trier.de)
