default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDSIAM Journal on Computing, Volume 27
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(22m). 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 Kahalé, 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 J. 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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-11-28 23:54 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
