Volume 27,
Number 1,
February 1998
- Frank Thomson Leighton, C. Greg Plaxton:
Hypercubic Sorting Networks.
1-47 BibTeX
- Johan Håstad:
The Shrinkage Exponent of de Morgan Formulas is 2.
48-64 BibTeX
- Hagit Attiya, Soma Chaudhuri, Roy Friedman, Jennifer L. Welch:
Shared Memory Consistency Conditions for Nonsequential Execution: Definitions and Programming Strategies.
65-89 BibTeX
- Amihood Amir, Gary Benson:
Two-Dimensional Periodicity in Rectangular Arrays.
90-106 BibTeX
- Martin L. Brady:
A Fast Discrete Approximation Algorithm for the Radon Transform.
107-119 BibTeX
- Thomas W. Cusick:
Value Sets of Some Polynomials Over Finite Fields GF(22m).
120-131 BibTeX
- Paola Bertolazzi, Giuseppe Di Battista, Carlo Mannino, Roberto Tamassia:
Optimal Upward Planarity Testing of Single-Source Digraphs.
132-169 BibTeX
- Samuel R. Buss, Peter N. Yianilos:
Linear and O(n log n) Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours.
170-201 BibTeX
- Robert D. Blumofe, Charles E. Leiserson:
Space-Efficient Scheduling of Multithreaded Computations.
202-229 BibTeX
- Mikael Goldmann, Marek Karpinski:
Simulating Threshold Circuits by Majority Circuits.
230-246 BibTeX
- Juan A. Garay, Yoram Moses:
Fully Polynomial Byzantine Agreement for n > 3t Processors in t + 1 Rounds.
247-290 BibTeX
- Yonatan Aumann, Yuval Rabani:
An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm.
291-301 BibTeX
- Juan A. Garay, Shay Kutten, David Peleg:
A Sublinear Time Distributed Algorithm for Minimum-Weight Spanning Trees.
302-316 BibTeX
Volume 27,
Number 2,
April 1998
- Hagit Attiya, Ophir Rachman:
Atomic Snapshots in O(n log n) Operations.
319-340 BibTeX
- Liming Cai, Jianer Chen, Johan Håstad:
Circuit Bottom Fan-In and Computational Power.
341-355 BibTeX
- Martin E. Dyer, Peter Gritzmann, Alexander Hufnagel:
On the Complexity of Computing Mixed Volumes.
356-400 BibTeX
- Nader H. Bshouty, Richard Cleve:
Interpolating Arithmetic Read-Once Formulas in Parallel.
401-413 BibTeX
- Rongheng Li, Lijie Shi:
An On-Line Algorithm for Some Uniform Processor Scheduling.
414-422 BibTeX
- Moni Naor, Avishai Wool:
The Load, Capacity, and Availability of Quorum Systems.
423-447 BibTeX
- Ioan I. Macarie:
Space-Efficient Deterministic Simulation of Probabilistic Automata.
448-465 BibTeX
- Phillip G. Bradford, Gregory J. E. Rawlins, Gregory E. Shannon:
Efficient Matrix Chain Ordering in Polylog Time.
466-490 BibTeX
- Pankaj K. Agarwal, Jirí Matousek, Otfried Schwarzkopf:
Computing Many Faces in Arrangements of Lines and Segments.
491-505 BibTeX
- Oded Goldreich, Shafi Goldwasser, Nathan Linial:
Fault-Tolerant Computation in the Full Information Model.
506-544 BibTeX
- Bernard Chazelle:
A Spectral Approach to Lower Bounds with Applications to Geometric Searching.
545-556 BibTeX
- Gad M. Landau, Eugene W. Myers, Jeanette P. Schmidt:
Incremental String Comparison.
557-582 BibTeX
- Gregory Dudek, Kathleen Romanik, Sue Whitesides:
Localizing a Robot with Minimum Travel.
583-604 BibTeX
Volume 27,
Number 3,
June 1998
- Ton Kloks, Dieter Kratsch:
Listing All Minimal Separators of a Graph.
605-613 BibTeX
- Hisao Tamaki:
Efficient Self-Embedding of Butterfly Networks with Random Faults.
614-636 BibTeX
- Harry Buhrman, Albrecht Hoene, Leen Torenvliet:
Splittings, Robustness, and Structure of Complete Sets.
637-653 BibTeX
- Pankaj K. Agarwal, Mark de Berg, Jirí Matousek, Otfried Schwarzkopf:
Constructing Levels in Arrangements and Higher Order Voronoi Diagrams.
654-667 BibTeX
- Maxime Crochemore, Leszek Gasieniec, Ramesh Hariharan, S. Muthukrishnan, Wojciech Rytter:
A Constant Time Optimal Parallel Algorithm for Two-Dimensional Pattern Matching.
668-681 BibTeX
- Susanne Albers:
Improved Randomized On-Line Algorithms for the List Update Problem.
682-693 BibTeX
- Dima Grigoriev, Marek Karpinski:
Computing the Additive Complexity of Algebraic Circuits with Root Extracting.
694-701 BibTeX
- Eyal Kushilevitz, Yishay Mansour:
An Omega(D log (N/D)) Lower Bound for Broadcast in Radio Networks.
702-712 BibTeX
- Paolo Ferragina, Roberto Grossi:
Optimal On-Line Search and Sublinear Time Update in String Matching.
713-736 BibTeX
- Shafi Goldwasser:
Introduction to Special Section on Probabilistic Proof Systems.
737-738 BibTeX
- Anne Condon, Lisa Hellerstein, Samuel Pottle, Avi Wigderson:
On the Power of Finite Automata with Both Nondeterministic and Probabilistic States.
739-762 BibTeX
- Ran Raz:
A Parallel Repetition Theorem.
763-803 BibTeX
- Mihir Bellare, Oded Goldreich, Madhu Sudan:
Free Bits, PCPs, and Nonapproximability-Towards Tight Results.
804-915 BibTeX
Volume 27,
Number 4,
August 1998
- Jean-Claude Bermond, Luisa Gargano, Adele A. Rescigno, Ugo Vaccaro:
Fast Gossiping by Short Messages.
917-941
Electronic Edition (link) BibTeX
- 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
Electronic Edition (link) BibTeX
- David Shallcross, Victor Y. Pan, Yu Lin-Kriz:
Planar Integer Linear Programming is NC Equivalent to Euclidean GCD.
960-971
Electronic Edition (link) BibTeX
- Jeanette P. Schmidt:
All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings.
972-992
Electronic Edition (link) BibTeX
- Ran Canetti, Sandy Irani:
Bounding the Power of Preemption in Randomized Scheduling.
993-1015
Electronic Edition (link) BibTeX
- Pankaj K. Agarwal, Subhash Suri:
Surface Approximation and Geometric Partitions.
1016-1035
Electronic Edition (link) BibTeX
- Mordecai J. Golin, Rajeev Raman, Christian Schwarz, Michiel H. M. Smid:
Randomized Data Structures for the Dynamic Closest-Pair Problem.
1036-1072
Electronic Edition (link) BibTeX
- Hing Leung:
Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata.
1073-1082
Electronic Edition (link) BibTeX
- Leslie Ann Goldberg, Mark Jerrum, Philip D. MacKenzie:
An Omega(sqrt{log log n}) Lower Bound for Routing in Optical Networks.
1083-1098
Electronic Edition (link) BibTeX
- Dario Bini, Victor Y. Pan:
Computing Matrix Eigenvalues and Polynomial Zeros Where the Output is Real.
1099-1115
Electronic Edition (link) BibTeX
- Oded Goldreich, Rafail Ostrovsky, Erez Petrank:
Computational Complexity and Knowledge Complexity.
1116-1141
Electronic Edition (link) BibTeX
- Harry B. Hunt III, Madhav V. Marathe, Venkatesh Radhakrishnan, Richard Edwin Stearns:
The Complexity of Planar Counting Problems.
1142-1167
Electronic Edition (link) BibTeX
- Amotz Bar-Noy, Alain J. Mayer, Baruch Schieber, Madhu Sudan:
Guaranteeing Fair Service to Persistent Dependent Tasks.
1168-1189
Electronic Edition (link) BibTeX
- Greg Barnes, Jeff Edmonds:
Time-Space Lower Bounds for Directed st-Connectivity on Graph Automata Models.
1190-1202
Electronic Edition (link) BibTeX
- David Gillman:
A Chernoff Bound for Random Walks on Expander Graphs.
1203-1220
Electronic Edition (link) BibTeX
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
Electronic Edition (link) BibTeX
- Madhav V. Marathe, Harry B. Hunt III, Richard Edwin Stearns, Venkatesh Radhakrishnan:
Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems.
1237-1261
Electronic Edition (link) BibTeX
- Martin E. Dyer, Alan M. Frieze, Mark Jerrum:
Approximately Counting Hamilton Paths and Cycles in Dense Graphs.
1262-1272
Electronic Edition (link) BibTeX
- Greg Barnes, Jonathan F. Buss, Walter L. Ruzzo, Baruch Schieber:
A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity.
1273-1282
Electronic Edition (link) BibTeX
- Mikael Goldmann, Johan Håstad:
Monotone Circuits for Connectivity Have Depth (log n)2-o(1).
1283-1294
Electronic Edition (link) BibTeX
- Christian Heckler, Lothar Thiele:
Complexity Analysis of a Parallel Lattice Basis Reduction Algorithm.
1295-1302
Electronic Edition (link) BibTeX
- Frank Thomson Leighton, Bruce M. Maggs, Ramesh K. Sitaraman:
On the Fault Tolerance of Some Popular Bounded-Degree Networks.
1303-1333
Electronic Edition (link) BibTeX
- Robert Beals, Tetsuro Nishino, Keisuke Tanaka:
On the Complexity of Negation-Limited Boolean Networks.
1334-1347
Electronic Edition (link) BibTeX
- Joseph Gil, Yossi Matias:
Simple Fast Parallel Hashing by Oblivious Execution.
1348-1375
Electronic Edition (link) BibTeX
- Mariangiola Dezani-Ciancaglini, Ugo de'Liguoro, Adolfo Piperno:
A Filter Model for Concurrent lambda-Calculus.
1376-1419
Electronic Edition (link) BibTeX
- Richard Beigel, Judy Goldsmith:
Downward Separation Fails Catastrophically for Limited Nondeterminism Classes.
1420-1429
Electronic Edition (link) BibTeX
- Mitsunori Ogihara:
The PL Hierarchy Collapses.
1430-1437
Electronic Edition (link) BibTeX
- Guy Kortsarz, David Peleg:
Generating Low-Degree 2-Spanners.
1438-1456
Electronic Edition (link) BibTeX
- Cynthia Dwork, Joseph Y. Halpern, Orli Waarts:
Performing Work Efficiently in the Presence of Faults.
1457-1491
Electronic Edition (link) BibTeX
- Jeff Edmonds:
Time-Space Tradeoffs For Undirected st-Connectivity on a Graph Automata.
1492-1513
Electronic Edition (link) BibTeX
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
Electronic Edition (link) BibTeX
- Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén:
Log-Space Polynomial End-to-End Communication.
1531-1549
Electronic Edition (link) BibTeX
- Eyal Kushilevitz, Yishay Mansour, Michael O. Rabin, David Zuckerman:
Lower Bounds for Randomized Mutual Exclusion.
1550-1563
Electronic Edition (link) BibTeX
- Tony W. Lai, Derick Wood:
Adaptive Heuristics for Binary Search Trees and Constant Linkage Cost.
1564-1591
Electronic Edition (link) BibTeX
- Ming-Yang Kao:
Tree Contractions and Evolutionary Trees.
1592-1616
Electronic Edition (link) BibTeX
- P. Krishnan, Jeffrey Scott Vitter:
Optimal Prediction for Prefetching in the Worst Case.
1617-1636
Electronic Edition (link) BibTeX
- Hagit Attiya, Roy Friedman:
A Correctness Condition for High-Performance Multiprocessors.
1637-1670
Electronic Edition (link) BibTeX
- Maw-Shang Chang:
Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs.
1671-1694
Electronic Edition (link) BibTeX
- Sampath Kannan, Tandy Warnow:
Computing the Local Consensus of Trees.
1695-1724
Electronic Edition (link) BibTeX
- Hans L. Bodlaender, Torben Hagerup:
Parallel Algorithms with Optimal Speedup for Bounded Treewidth.
1725-1746
Electronic Edition (link) BibTeX
- Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht:
First-Order Queries on Finite Structures Over the Reals.
1747-1763
Electronic Edition (link) BibTeX
- Giuseppe Di Battista, Giuseppe Liotta, Francesco Vargiu:
Spirality and Optimal Orthogonal Drawings.
1764-1811
Electronic Edition (link) BibTeX
Copyright © Sun May 17 00:18:55 2009
by Michael Ley (ley@uni-trier.de)