Volume 26, Number 1, February 1997
- Laurent Alonso, Edward M. Reingold, René Schott:
The Average-Case Complexity of Determining the Majority.
1-14 BibTeX
- Moshe Dubiner, Uri Zwick:
Amplification by Read-Once Formulas.
15-38 BibTeX
- Maurice Nivat, Andreas Podelski:
Minimal Ascending and Descending Tree Automata.
39-58 BibTeX
- Yenjo Han, Lane A. Hemaspaandra, Thomas Thierauf:
Threshold Computation and Cryptographic Security.
59-78 BibTeX
- Zhengyu Ge, S. Louis Hakimi:
Disjoint Rooted Spanning Trees with Small Depths in deBruijn and Kautz Graphs.
79-92 BibTeX
- Endre Boros, Peter L. Hammer, Toshihide Ibaraki, Kazuhiko Kawakami:
Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle.
93-109 BibTeX
- Avrim Blum, Prabhakar Raghavan, Baruch Schieber:
Navigating in Unfamiliar Geometric Terrain.
110-137 BibTeX
- Martin Beaudry, Pierre McKenzie, Pierre Péladeau, Denis Thérien:
Finite Moniods: From Word to Circuit Evaluation.
138-152 BibTeX
- Louis Mak:
Parallelism Always Helps.
153-172 BibTeX
- Zhen Liu, Eric Sanlaville:
Stochastic Scheduling with Variable Profile and Precedence Constraints.
173-187 BibTeX
- Richard Chang, William I. Gasarch, Carsten Lund:
On Bounded Queries and Approximation.
188-209 BibTeX
- Martin Farach, Mikkel Thorup:
Sparse Dynamic Programming for Evolutionary-Tree Comparison.
210-230 BibTeX
- Ming-Yang Kao:
Total Protection of Analytic-Invariant Information in Cross-Tabulated Tables.
231-242 BibTeX
- Felipe Cucker, Dima Grigoriev:
On the Power of Real Turing Machines Over Binary Inputs.
243-254 BibTeX
- David R. Karger, Rajeev Motwani:
An NC Algorithm for Minimum Cuts.
255-272 BibTeX
- Shlomi Dolev, Amos Israeli, Shlomo Moran:
Resource Bounds for Self-Stabilizing Message-Driven Protocols.
273-290 BibTeX
Volume 26, Number 2, April 1997
- Torben P. Pedersen, Birgit Pfitzmann:
Fail-Stop Signatures.
291-330 BibTeX
- Heike Ripphausen-Lipa, Dorothea Wagner, Karsten Weihe:
The Vertex-Disjoint Menger Problem in Planar Graphs.
331-349 BibTeX
- Alessandro Panconesi, Aravind Srinivasan:
Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds.
350-368 BibTeX
- Anne Condon, Joan Feigenbaum, Carsten Lund, Peter W. Shor:
Random Debaters and the Hardness of Approximating Stochastic Functions.
369-400 BibTeX
- A. Steinberg:
A Strip-Packing Algorithm with Absolute Performance Bound 2.
401-409 BibTeX
- Shang-Hua Teng, F. Frances Yao:
Approximating Shortest Superstrings.
410-417 BibTeX
- Danny Dolev, Nir Shavit:
Bounded Concurrent Time-Stamping.
418-455 BibTeX
- Paul Walton Purdom Jr., G. Neil Haven:
Probe Order Backtracking.
456-483 BibTeX
- Greg N. Frederickson:
Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees.
484-538 BibTeX
- Rajeev Alur, Hagit Attiya, Gadi Taubenfeld:
Time-Adaptive Algorithms for Synchronization.
539-556 BibTeX
- Eric Allender, José L. Balcázar, Neil Immerman:
A First-Order Isomorphism Theorem.
557-567 BibTeX
- Rakesh M. Verma:
General Techniques for Analyzing Recursive Algorithms with Applications.
568-581 BibTeX
- András Sebö:
Potentials in Undirected Graphs and Planar Multiflows.
582-603 BibTeX
Volume 26, Number 3, June 1997
- Pavel Pudlák, Vojtech Rödl, Jiri Sgall:
Boolean Circuits, Tensor Ranks, and Communication Complexity.
605-633 BibTeX
- Lane A. Hemaspaandra, Jörg Rothe:
Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets.
634-653 BibTeX
- Shai Mohaban, Micha Sharir:
Ray Shooting Amidst Spheres in Three Dimensions and Related Problems.
654-674 BibTeX
- Carsten Thomassen:
On the Complexity of Finding a Minimum Cycle Cover of a Graph.
675-677 BibTeX
- Akiyoshi Shioura, Akihisa Tamura, Takeaki Uno:
An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs.
678-692 BibTeX
- Russell Impagliazzo, Ramamohan Paturi, Michael E. Saks:
Size-Depth Tradeoffs for Threshold Circuits.
693-707 BibTeX
- Wolfgang Maass:
Bounds for the Computational Power and Learning Complexity of Analog Neural Nets.
708-732 BibTeX
- Liming Cai, Jianer Chen:
On the Amount of Nondeterminism and the Power of Verifying.
733-750 BibTeX
- Hans-Ulrich Simon:
Bounds on the Number of Examples Needed for Learning Functions.
751-763 BibTeX
- Stefano Varricchio:
A Pumping Condition for Regular Sets.
764-771 BibTeX
- Gurdip Singh:
Leader Election in Complete Networks.
772-785 BibTeX
- Xiaotie Deng, Sanjeev Mahajan:
The Cost of Derandomization: Computability or Competitiveness.
786-802 BibTeX
- Richard Cole, Ramesh Hariharan:
Tighter Upper Bounds on the Exact Complexity of String Matching.
803-856 BibTeX
- Al Borchers, Ding-Zhu Du:
The k-Steiner Ratio in Graphs.
857-869 BibTeX
- 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 BibTeX
Volume 26, Number 4, August 1997
- Pesech Feldman, Silvio Micali:
An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement.
873-933 BibTeX
- James A. Storer, John H. Reif:
Error-Resilient Optimal Data Compression.
934-949 BibTeX
- Maxime Crochemore, Zvi Galil, Leszek Gasieniec, Kunsoo Park, Wojciech Rytter:
Constant-Time Randomized Parallel String Matching.
950-960 BibTeX
- Ganesh Baliga, Sanjay Jain, Arun Sharma:
Learning from Multiple Sources of Inaccurate Data.
961-990 BibTeX
- Michal Walicki, Sigurd Meldal:
Singular and Plural Nondeterministic Parameters.
991-1005 BibTeX
- Guy Louchard, Claire Kenyon, René Schott:
Data Structures' Maxima.
1006-1042 BibTeX
- Stephen A. Fenner, Steven Homer, Mitsunori Ogihara, Alan L. Selman:
Oracles that Compute Values.
1043-1065 BibTeX
- 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 BibTeX
- Leslie Ann Goldberg, Mark Jerrum, Frank Thomson Leighton, Satish Rao:
Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel Computers.
1100-1119 BibTeX
- Leonidas J. Guibas, Rajeev Motwani, Prabhakar Raghavan:
The Robot Localization Problem.
1120-1138 BibTeX
- Dalit Naor, Dan Gusfield, Charles U. Martel:
A Fast Algorithm for Optimally Increasing the Edge Connectivity.
1139-1165 BibTeX
- Dorit Dor, Michael Tarsi:
Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture.
1166-1187 BibTeX
- Bonnie Berger:
The Fourth Moment Method.
1188-1207 BibTeX
- Phillip B. Gibbons, Ephraim Korach:
Testing Shared Memories.
1208-1244 BibTeX
- Alexander V. Karzanov, S. Thomas McCormick:
Polynomial Methods for Separable Convex Optimization in Unimodular Linear Spaces with Applications.
1245-1275 BibTeX
Volume 26, Number 5, October 1997
- Richard J. Anderson, Heather Woll:
Algorithms for the Certified Write-All Problem.
1277-1283 BibTeX
- Sam M. Kim:
Computational Modeling for Genetic Splicing Systems.
1284-1309 BibTeX
- László Babai, Eugene M. Luks, Ákos Seress:
Fast Management of Permutation Groups I.
1310-1342 BibTeX
- Brenda S. Baker:
Parameterized Duplication in Strings: Algorithms and an Application to Software Maintenance.
1343-1362 BibTeX
- Kazuhisa Makino, Toshihide Ibaraki:
The Maximum Latency and Identification of Positive Boolean Functions.
1363-1383 BibTeX
- Matthew J. Katz, Micha Sharir:
An Expander-Based Approach to Geometric Optimization.
1384-1408 BibTeX
- Umesh V. Vazirani:
Introduction to Special Section on Quantum Computation.
1409-1410 BibTeX
- Ethan Bernstein, Umesh V. Vazirani:
Quantum Complexity Theory.
1411-1473 BibTeX
- Daniel R. Simon:
On the Power of Quantum Computation.
1474-1483 BibTeX
- Peter W. Shor:
Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.
1484-1509 BibTeX
- Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh V. Vazirani:
Strengths and Weaknesses of Quantum Computing.
1510-1523 BibTeX
- Leonard M. Adleman, Jonathan DeMarrais, Ming-Deh A. Huang:
Quantum Computability.
1524-1540 BibTeX
- Adriano Barenco, André Berthiaume, David Deutsch, Artur Ekert, Richard Jozsa, Chiara Macchiavello:
Stabilization of Quantum Computations by Symmetrization.
1541-1557 BibTeX
Volume 26, Number 6, December 1997
- Philip D. MacKenzie:
The Random Adversary: A Lower-Bound Technique for Randomized Parallel Algorithms.
1559-1580 BibTeX
- Richard J. Cole, Bruce M. Maggs, Ramesh K. Sitaraman:
Reconfiguring Arrays with Faults Part I: Worst-Case Faults.
1581-1611 BibTeX
- John Hershberger, Subhash Suri:
Matrix Searching with the Shortest-Path Metric.
1612-1634 BibTeX
- Joseph Cheriyan:
Randomized Õ(M(|V|)) Algorithms for Problems in Matching Theory.
1635-1669 BibTeX
- Amihood Amir, Dmitry Keselman:
Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms.
1656-1669 BibTeX
- Boris Aronov, Micha Sharir, Boaz Tagansky:
The Union of Convex Polyhedra in Three Dimensions.
1670-1688 BibTeX
- Pankaj K. Agarwal, Boris Aronov, Joseph O'Rourke, Catherine A. Schevon:
Star Unfolding of a Polytope with Applications.
1689-1713 BibTeX
- Pankaj K. Agarwal, Boris Aronov, Micha Sharir:
Computing Envelopes in Four Dimensions with Applications.
1714-1732 BibTeX
- Noga Alon, Nabil Kahale:
A Spectral Technique for Coloring Random 3-Colorable Graphs.
1733-1748 BibTeX
- Sampath Kannan, Tandy Warnow:
A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies.
1749-1763 BibTeX
- Jehoshua Bruck, Robert Cypher, Ching-Tien Ho:
Fault-Tolerant Meshes with Small Degree.
1764-1784 BibTeX
- Boris Aronov, Micha Sharir:
On Translational Motion Planning of a Convex Polyhedron in 3-Space.
1785-1803 BibTeX
Copyright © Wed Jun 4 19:18:25 2008
by Michael Ley (ley@uni-trier.de)
