Volume 27, Number 1, February 1998

• 
  Frank Thomson Leighton, C. Greg Plaxton: Hypercubic Sorting Networks. 1-47
• 
  Johan Håstad: The Shrinkage Exponent of de Morgan Formulas is 2. 48-64
• 
  Hagit Attiya, Soma Chaudhuri, Roy Friedman, Jennifer L. Welch: Shared Memory Consistency Conditions for Nonsequential Execution: Definitions and Programming Strategies. 65-89
• 
  Amihood Amir, Gary Benson: Two-Dimensional Periodicity in Rectangular Arrays. 90-106
• 
  Martin L. Brady: A Fast Discrete Approximation Algorithm for the Radon Transform. 107-119
• 
  Thomas W. Cusick: Value Sets of Some Polynomials Over Finite Fields GF(2^2m). 120-131
• 
  Paola Bertolazzi, Giuseppe Di Battista, Carlo Mannino, Roberto Tamassia: Optimal Upward Planarity Testing of Single-Source Digraphs. 132-169
• 
  Samuel R. Buss, Peter N. Yianilos: Linear and O(n log n) Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours. 170-201
• 
  Robert D. Blumofe, Charles E. Leiserson: Space-Efficient Scheduling of Multithreaded Computations. 202-229
• 
  Mikael Goldmann, Marek Karpinski: Simulating Threshold Circuits by Majority Circuits. 230-246
• 
  Juan A. Garay, Yoram Moses: Fully Polynomial Byzantine Agreement for n > 3t Processors in t + 1 Rounds. 247-290
• 
  Yonatan Aumann, Yuval Rabani: An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm. 291-301
• 
  Juan A. Garay, Shay Kutten, David Peleg: A Sublinear Time Distributed Algorithm for Minimum-Weight Spanning Trees. 302-316

Volume 27, Number 2, April 1998

• 
  Hagit Attiya, Ophir Rachman: Atomic Snapshots in O(n log n) Operations. 319-340
• 
  Liming Cai, Jianer Chen, Johan Håstad: Circuit Bottom Fan-In and Computational Power. 341-355
• 
  Martin E. Dyer, Peter Gritzmann, Alexander Hufnagel: On the Complexity of Computing Mixed Volumes. 356-400
• 
  Nader H. Bshouty, Richard Cleve: Interpolating Arithmetic Read-Once Formulas in Parallel. 401-413
• 
  Rongheng Li, Lijie Shi: An On-Line Algorithm for Some Uniform Processor Scheduling. 414-422
• 
  Moni Naor, Avishai Wool: The Load, Capacity, and Availability of Quorum Systems. 423-447
• 
  Ioan I. Macarie: Space-Efficient Deterministic Simulation of Probabilistic Automata. 448-465
• 
  Phillip G. Bradford, Gregory J. E. Rawlins, Gregory E. Shannon: Efficient Matrix Chain Ordering in Polylog Time. 466-490
• 
  Pankaj K. Agarwal, Jirí Matousek, Otfried Schwarzkopf: Computing Many Faces in Arrangements of Lines and Segments. 491-505
• 
  Oded Goldreich, Shafi Goldwasser, Nathan Linial: Fault-Tolerant Computation in the Full Information Model. 506-544
• 
  Bernard Chazelle: A Spectral Approach to Lower Bounds with Applications to Geometric Searching. 545-556
• 
  Gad M. Landau, Eugene W. Myers, Jeanette P. Schmidt: Incremental String Comparison. 557-582
• 
  Gregory Dudek, Kathleen Romanik, Sue Whitesides: Localizing a Robot with Minimum Travel. 583-604

Volume 27, Number 3, June 1998

• 
  Ton Kloks, Dieter Kratsch: Listing All Minimal Separators of a Graph. 605-613
• 
  Hisao Tamaki: Efficient Self-Embedding of Butterfly Networks with Random Faults. 614-636
• 
  Harry Buhrman, Albrecht Hoene, Leen Torenvliet: Splittings, Robustness, and Structure of Complete Sets. 637-653
• 
  Pankaj K. Agarwal, Mark de Berg, Jirí Matousek, Otfried Schwarzkopf: Constructing Levels in Arrangements and Higher Order Voronoi Diagrams. 654-667
• 
  Maxime Crochemore, Leszek Gasieniec, Ramesh Hariharan, S. Muthukrishnan, Wojciech Rytter: A Constant Time Optimal Parallel Algorithm for Two-Dimensional Pattern Matching. 668-681
• 
  Susanne Albers: Improved Randomized On-Line Algorithms for the List Update Problem. 682-693
• 
  Dima Grigoriev, Marek Karpinski: Computing the Additive Complexity of Algebraic Circuits with Root Extracting. 694-701
• 
  Eyal Kushilevitz, Yishay Mansour: An Omega(D log (N/D)) Lower Bound for Broadcast in Radio Networks. 702-712
• 
  Paolo Ferragina, Roberto Grossi: Optimal On-Line Search and Sublinear Time Update in String Matching. 713-736
• 
  Shafi Goldwasser: Introduction to Special Section on Probabilistic Proof Systems. 737-738
• 
  Anne Condon, Lisa Hellerstein, Samuel Pottle, Avi Wigderson: On the Power of Finite Automata with Both Nondeterministic and Probabilistic States. 739-762
• 
  Ran Raz: A Parallel Repetition Theorem. 763-803
• 
  Mihir Bellare, Oded Goldreich, Madhu Sudan: Free Bits, PCPs, and Nonapproximability-Towards Tight Results. 804-915

Volume 27, Number 4, August 1998

• 
  Jean-Claude Bermond, Luisa Gargano, Adele A. Rescigno, Ugo Vaccaro: Fast Gossiping by Short Messages. 917-941
• 
  Reuven Bar-Yehuda, Dan Geiger, Joseph Naor, Ron M. Roth: Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference. 942-959
• 
  David Shallcross, Victor Y. Pan, Yu Lin-Kriz: Planar Integer Linear Programming is NC Equivalent to Euclidean GCD. 960-971
• 
  Jeanette P. Schmidt: All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings. 972-992
• 
  Ran Canetti, Sandy Irani: Bounding the Power of Preemption in Randomized Scheduling. 993-1015
• 
  Pankaj K. Agarwal, Subhash Suri: Surface Approximation and Geometric Partitions. 1016-1035
• 
  Mordecai J. Golin, Rajeev Raman, Christian Schwarz, Michiel H. M. Smid: Randomized Data Structures for the Dynamic Closest-Pair Problem. 1036-1072
• 
  Hing Leung: Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata. 1073-1082
• 
  Leslie Ann Goldberg, Mark Jerrum, Philip D. MacKenzie: An Omega(sqrt{log log n}) Lower Bound for Routing in Optical Networks. 1083-1098
• 
  Dario Bini, Victor Y. Pan: Computing Matrix Eigenvalues and Polynomial Zeros Where the Output is Real. 1099-1115
• 
  Oded Goldreich, Rafail Ostrovsky, Erez Petrank: Computational Complexity and Knowledge Complexity. 1116-1141
• 
  Harry B. Hunt III, Madhav V. Marathe, Venkatesh Radhakrishnan, Richard Edwin Stearns: The Complexity of Planar Counting Problems. 1142-1167
• 
  Amotz Bar-Noy, Alain J. Mayer, Baruch Schieber, Madhu Sudan: Guaranteeing Fair Service to Persistent Dependent Tasks. 1168-1189
• 
  Greg Barnes, Jeff Edmonds: Time-Space Lower Bounds for Directed st-Connectivity on Graph Automata Models. 1190-1202
• 
  David Gillman: A Chernoff Bound for Random Walks on Expander Graphs. 1203-1220

Volume 27, Number 5, October 1998

• 
  Edward G. Coffman Jr., Nabil Kahale, Frank Thomson Leighton: Processor-Ring Communication: A Tight Asymptotic Bound on Packet Waiting Times. 1221-1236
• 
  Madhav V. Marathe, Harry B. Hunt III, Richard Edwin Stearns, Venkatesh Radhakrishnan: Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems. 1237-1261
• 
  Martin E. Dyer, Alan M. Frieze, Mark Jerrum: Approximately Counting Hamilton Paths and Cycles in Dense Graphs. 1262-1272
• 
  Greg Barnes, Jonathan F. Buss, Walter L. Ruzzo, Baruch Schieber: A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity. 1273-1282
• 
  Mikael Goldmann, Johan Håstad: Monotone Circuits for Connectivity Have Depth (log n)^2-o(1). 1283-1294
• 
  Christian Heckler, Lothar Thiele: Complexity Analysis of a Parallel Lattice Basis Reduction Algorithm. 1295-1302
• 
  Frank Thomson Leighton, Bruce M. Maggs, Ramesh K. Sitaraman: On the Fault Tolerance of Some Popular Bounded-Degree Networks. 1303-1333
• 
  Robert Beals, Tetsuro Nishino, Keisuke Tanaka: On the Complexity of Negation-Limited Boolean Networks. 1334-1347
• 
  Joseph Gil, Yossi Matias: Simple Fast Parallel Hashing by Oblivious Execution. 1348-1375
• 
  Mariangiola Dezani-Ciancaglini, Ugo de'Liguoro, Adolfo Piperno: A Filter Model for Concurrent lambda-Calculus. 1376-1419
• 
  Richard Beigel, Judy Goldsmith: Downward Separation Fails Catastrophically for Limited Nondeterminism Classes. 1420-1429
• 
  Mitsunori Ogihara: The PL Hierarchy Collapses. 1430-1437
• 
  Guy Kortsarz, David Peleg: Generating Low-Degree 2-Spanners. 1438-1456
• 
  Cynthia Dwork, Joseph Y. Halpern, Orli Waarts: Performing Work Efficiently in the Presence of Faults. 1457-1491
• 
  Jeff Edmonds: Time-Space Tradeoffs For Undirected st-Connectivity on a Graph Automata. 1492-1513

Volume 27, Number 6, December 1998

• 
  Howard Aizenstein, Avrim Blum, Roni Khardon, Eyal Kushilevitz, Leonard Pitt, Dan Roth: On Learning Read-k-Satisfy-j DNF. 1515-1530
• 
  Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén: Log-Space Polynomial End-to-End Communication. 1531-1549
• 
  Eyal Kushilevitz, Yishay Mansour, Michael O. Rabin, David Zuckerman: Lower Bounds for Randomized Mutual Exclusion. 1550-1563
• 
  Tony W. Lai, Derick Wood: Adaptive Heuristics for Binary Search Trees and Constant Linkage Cost. 1564-1591
• 
  Ming-Yang Kao: Tree Contractions and Evolutionary Trees. 1592-1616
• 
  P. Krishnan, Jeffrey Scott Vitter: Optimal Prediction for Prefetching in the Worst Case. 1617-1636
• 
  Hagit Attiya, Roy Friedman: A Correctness Condition for High-Performance Multiprocessors. 1637-1670
• 
  Maw-Shang Chang: Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs. 1671-1694
• 
  Sampath Kannan, Tandy Warnow: Computing the Local Consensus of Trees. 1695-1724
• 
  Hans L. Bodlaender, Torben Hagerup: Parallel Algorithms with Optimal Speedup for Bounded Treewidth. 1725-1746
• 
  Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht: First-Order Queries on Finite Structures Over the Reals. 1747-1763
• 
  Giuseppe Di Battista, Giuseppe Liotta, Francesco Vargiu: Spirality and Optimal Orthogonal Drawings. 1764-1811

last updated on Wed May 22 06:07:11 2013 by the dblp team
data released under the ODC-BY 1.0 license
see also our legal information page