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 Wed May 22 18:17:26 2013
CET by the DBLP Team —
Data released under the ODC-BY 1.0 license — See also our legal information page