SIAM Journal on Computing, Volume 30

Volume 30, Number 1, 2000

Richard Cole, Bud Mishra, Jeanette P. Schmidt, Alan Siegel: On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences. 1-43 BibTeX
Richard Cole: On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof. 44-85 BibTeX
Mikkel Thorup: On RAM Priority Queues. 86-109 BibTeX
Dana Angluin, Jeffery Westbrook, Wenhong Zhu: Robot Navigation with Distance Queries. 110-144 BibTeX
Xiaotie Deng, Nian Gu, Tim Brecht, KaiCheng Lu: Preemptive Scheduling of Parallel Jobs on Multiprocessors. 145-160 BibTeX
John H. Reif, Hongyan Wang: Nonuniform Discretization for Kinodynamic Motion Planning and its Applications. 161-190 BibTeX
Jon M. Kleinberg, Yuval Rabani, Éva Tardos: Allocating Bandwidth for Bursty Connections. 191-217 BibTeX
Jean-Daniel Boissonnat, Olivier Devillers, Sylvain Lazard: Motion Planning of Legged Robots. 218-246 BibTeX
Shay Kutten, David Peleg: Tight Fault Locality. 247-268 BibTeX
David Greenhalgh, Stephen Marshall: Convergence Criteria for Genetic Algorithms. 269-282 BibTeX
Lusheng Wang, Tao Jiang, Dan Gusfield: A More Efficient Approximation Scheme for Tree Alignment. 283-299 BibTeX
Elias Koutsoupias, Christos H. Papadimitriou: Beyond Competitive Analysis. 300-317 BibTeX
Michelangelo Grigni, Vincent Mirelli, Christos H. Papadimitriou: On the Difficulty of Designing Good Classifiers. 318-323 BibTeX
Uriel Feige, Joe Kilian: Two-Prover Protocols - Low Error at Affordable Rates. 324-346 BibTeX

Volume 30, Number 2, 2000

Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber: Message Multicasting in Heterogeneous Networks. 347-358 BibTeX
Clifford Bergman, Giora Slutzki: Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras. 359-382 BibTeX
Claudia Bertram-Kretzberg, Thomas Hofmeister, Hanno Lefmann: An Algorithm for Heilbronn's Problem. 383-390 BibTeX
Danny Dolev, Cynthia Dwork, Moni Naor: Nonmalleable Cryptography. 391-437 BibTeX
Prasad Jayanti, King Tan, Sam Toueg: Time and Space Lower Bounds for Nonblocking Implementations. 438-456 BibTeX
Eyal Kushilevitz, Rafail Ostrovsky, Yuval Rabani: Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces. 457-474 BibTeX
Luca Trevisan: When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree. 475-485 BibTeX
George Varghese: Self-Stabilization by Counter Flushing. 486-510 BibTeX
Gilad Koren, Emanuel Dar, Amihood Amir: The Power of Migration in Multiprocessor Scheduling of Real-Time Systems. 511-527 BibTeX
Joseph Cheriyan, Ramakrishna Thurimella: Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching. 528-560 BibTeX
Timothy M. Chan: Random Sampling, Halfspace Range Reporting, and Construction of (<= k)-Levels in Three Dimensions. 561-575 BibTeX
Harry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss: A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem. 576-601 BibTeX
Ming-Yang Kao, Tak Wah Lam, Wing-Kin Sung, Hing-Fung Ting: Cavity Matchings, Label Compressions, and Unrooted Evolutionary Trees. 602-624 BibTeX
Andrea Pietracaprina, Geppino Pucci, Jop F. Sibeyn: Constructive, Deterministic Implementation of Shared Memory on Meshes. 625-648 BibTeX
Harold N. Gabow, Tibor Jordán: How to Make a Square Grid Framework with Cables Rigid. 649-680 BibTeX
Nah-Oak Song, Demosthenis Teneketzis: On a Conjecture by Coffman, Flatto, and Wright on Stochastic Machine Minimization. 681-687 BibTeX

Volume 30, Number 3, 2000

Wai-Kau Lo, Vassos Hadzilacos:
All of Us Are Smarter than Any of Us: Nondeterministic Wait-Free Hierarchies Are Not Robust. 689-728
Electronic Edition (link) BibTeX
Bin Ma, Ming Li, Louxin Zhang:
From Gene Trees to Species Trees. 729-752
Electronic Edition (link) BibTeX
Yefim Dinitz, Alek Vainshtein:
The General Structure of Edge-Connectivity of a Vertex Subset in a Graph and its Incremental Maintenance. Odd Case. 753-808
Electronic Edition (link) BibTeX
Christopher L. Barrett, Riko Jacob, Madhav V. Marathe:
Formal-Language-Constrained Path Problems. 809-837
Electronic Edition (link) BibTeX
Xin He, Ming-Yang Kao, Hsueh-I Lu:
A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs. 838-846
Electronic Edition (link) BibTeX
Sanjiv Kapoor, S. N. Maheshwari:
Efficiently Constructing the Visibility Graph of a Simple Polygon with Obstacles. 847-871
Electronic Edition (link) BibTeX
Håkan Lennerstad, Lars Lundberg:
Optimal Worst Case Formulas Comparing Cache Memory Associativity. 872-905
Electronic Edition (link) BibTeX
Anna R. Karlin, Steven J. Phillips, Prabhakar Raghavan:
Markov Paging. 906-922
Electronic Edition (link) BibTeX
Charles Knessl, Wojciech Szpankowski:
Asymptotic Behavior of the Height in a Digital Search Tree and the Longest Phrase of the Lempel-Ziv Scheme. 923-964
Electronic Edition (link) BibTeX
Haim Kaplan, Chris Okasaki, Robert Endre Tarjan:
Simple Confluently Persistent Catenable Lists. 965-977
Electronic Edition (link) BibTeX
Giri Narasimhan, Michiel H. M. Smid:
Approximating the Stretch Factor of Euclidean Graphs. 978-989
Electronic Edition (link) BibTeX
Manindra Agrawal, Thomas Thierauf:
The Formula Isomorphism Problem. 990-1009
Electronic Edition (link) BibTeX
Peter Bürgisser:
The Computational Complexity to Evaluate Representations of General Linear Groups. 1010-1022
Electronic Edition (link) BibTeX
Peter Bürgisser:
The Computational Complexity of Immanants. 1023-1040
Electronic Edition (link) BibTeX

Volume 30, Number 4, 2000

Andrzej Czygrinow, Vojtech Rödl:
An Algorithmic Regularity Lemma for Hypergraphs. 1041-1066
Electronic Edition (link) BibTeX
Assaf Natanzon, Ron Shamir, Roded Sharan:
A Polynomial Approximation Algorithm for the Minimum Fill-In Problem. 1067-1079
Electronic Edition (link) BibTeX
Victor Y. Pan:
Parallel Complexity of Computations with General and Toeplitz-Like Matrices Filled with Integers and Extensions. 1080-1125
Electronic Edition (link) BibTeX
Christian Scheideler, Berthold Vöcking:
From Static to Dynamic Routing: Efficient Transformations of Store-and-Forward Protocols. 1126-1155
Electronic Edition (link) BibTeX
Eric Ruppert:
Determining Consensus Numbers. 1156-1168
Electronic Edition (link) BibTeX
Amir Herzberg, Shay Kutten:
Early Detection of Message Forwarding Faults. 1169-1196
Electronic Edition (link) BibTeX
Jack H. Lutz, Yong Zhao:
The Density of Weakly Complete Problems under Adaptive Reductions. 1197-1210
Electronic Edition (link) BibTeX
Frédérique Bassino, Marie-Pierre Béal, Dominique Perrin:
A Finite State Version of the Kraft--McMillan Theorem. 1211-1230
Electronic Edition (link) BibTeX
Guy Even, Joseph Naor, Leonid Zosin:
An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem. 1231-1252
Electronic Edition (link) BibTeX
Silvio Micali:
Computationally Sound Proofs. 1253-1298
Electronic Edition (link) BibTeX
Vikraman Arvind, Richard Beigel, Antoni Lozano:
The Complexity of Modular Graph Automorphism. 1299-1320
Electronic Edition (link) BibTeX
Kasturi R. Varadarajan, Pankaj K. Agarwal:
Approximating Shortest Paths on a Nonconvex Polyhedron. 1321-1340
Electronic Edition (link) BibTeX
Sariel Har-Peled:
Taking a Walk in a Planar Arrangement. 1341-1367
Electronic Edition (link) BibTeX
Xiaoxu Han, Suely Oliveira, David E. Stewart:
Finding Sets Covering a Point with Application to Mesh-Free Galerkin Methods. 1368-1383
Electronic Edition (link) BibTeX

Volume 30, Number 5, 2000

Richard Cole, Martin Farach-Colton, Ramesh Hariharan, Teresa M. Przytycka, Mikkel Thorup:
An O(nlog n) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees. 1385-1404
Electronic Edition (link) BibTeX
Ruy Luiz Milidiú, Eduardo Sany Laber:
The WARM-UP Algorithm: A Lagrangian Construction of Length Restricted Huffman Codes. 1405-1426
Electronic Edition (link) BibTeX
David Peleg, Vitaly Rubinovich:
A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction. 1427-1442
Electronic Edition (link) BibTeX
Martin E. Dyer, Sandeep Sen:
Fast and Optimal Parallel Multidimensional Search in PRAMs with Applications to Linear Programming and Related Problems. 1443-1461
Electronic Edition (link) BibTeX
Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, Jan Johannsen:
On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems. 1462-1484
Electronic Edition (link) BibTeX
Harry Buhrman, Leen Torenvliet:
Randomness is Hard. 1485-1501
Electronic Edition (link) BibTeX
Adam L. Buchsbaum, Raffaele Giancarlo, Jeffery Westbrook:
On the Determinization of Weighted Finite Automata. 1502-1531
Electronic Edition (link) BibTeX
Giorgio Gambosi, Alberto Postiglione, Maurizio Talamo:
Algorithms for the Relaxed Online Bin-Packing Model. 1532-1551
Electronic Edition (link) BibTeX
Arne Andersson, Torben Hagerup, Johan Håstad, Ola Petersson:
Tight Bounds for Searching a Sorted Array of Strings. 1552-1578
Electronic Edition (link) BibTeX
Marcus Brazil, D. A. Thomas, J. F. Weng:
Minimum Networks in Uniform Orientation Metrics. 1579-1593
Electronic Edition (link) BibTeX
Matthew Andrews, Antonio Fernández, Mor Harchol-Balter, Frank Thomson Leighton, Lisa Zhang:
General Dynamic Routing with Per-Packet Delay Guarantees of O(Distance + 1/Session Rate). 1594-1623
Electronic Edition (link) BibTeX
Avrim Blum, Howard J. Karloff, Yuval Rabani, Michael E. Saks:
A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems. 1624-1661
Electronic Edition (link) BibTeX
Andreas Brandstädt, Feodor F. Dragan, Ekkehard Köhler:
Linear Time Algorithms for Hamiltonian Problems on (Claw, Net)-Free Graphs. 1662-1677
Electronic Edition (link) BibTeX
Luc Devroye, Jean Jabbour, Carlos Zamora-Cura:
Squarish k-d Trees. 1678-1700
Electronic Edition (link) BibTeX
Bruno Gaujal, Alain Jean-Marie, Jean Mairesse:
Computations of Uniform Recurrence Equations Using Minimal Memory Size. 1701-1738
Electronic Edition (link) BibTeX

Volume 30, Number 6, 2000

Pankaj K. Agarwal, Hongyan Wang:
Approximation Algorithms for Curvature-Constrained Shortest Paths. 1739-1772
Electronic Edition (link) BibTeX
Farhad Shahrokhi, Ondrej Sýkora, László A. Székely, Imrich Vrto:
On Bipartite Drawings and the Linear Arrangement Problem. 1773-1789
Electronic Edition (link) BibTeX
Alan M. Frieze:
Edge-Disjoint Paths in Expander Graphs. 1790-1801
Electronic Edition (link) BibTeX
Omer Berkman, Michal Parnas, Jiri Sgall:
Efficient Dynamic Traitor Tracing. 1802-1828
Electronic Edition (link) BibTeX
Harry Buhrman, Richard Cleve, Wim van Dam:
Quantum Entanglement and Communication Complexity. 1829-1841
Electronic Edition (link) BibTeX
Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy:
Regular Languages are Testable with a Constant Number of Queries. 1842-1862
Electronic Edition (link) BibTeX
Sanjeev Khanna, Madhu Sudan, Luca Trevisan, David P. Williamson:
The Approximability of Constraint Satisfaction Problems. 1863-1920
Electronic Edition (link) BibTeX
Waleed Meleis:
Dual-Issue Scheduling for Binary Trees with Spills and Pipelined Loads. 1921-1941
Electronic Edition (link) BibTeX
Tao Jiang, Paul E. Kearney, Ming Li:
A Polynomial Time Approximation Scheme for Inferring Evolutionary Trees from Quartet Topologies and Its Application. 1942-1961
Electronic Edition (link) BibTeX
Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum, Michael Mitzenmacher:
An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colorings. 1962-1975
Electronic Edition (link) BibTeX
Carlo Mereghetti, Giovanni Pighizzini:
Optimal Simulations between Unary Automata. 1976-1992
Electronic Edition (link) BibTeX
Mao-cheng Cai, Xiaotie Deng, Wenan Zang:
An Approximation Algorithm for Feedback Vertex Sets in Tournaments. 1993-2007
Electronic Edition (link) BibTeX
Daniele Micciancio:
The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant. 2008-2035
Electronic Edition (link) BibTeX
Endre Boros, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino:
Dual-Bounded Generating Problems: Partial and Multiple Transversals of a Hypergraph. 2036-2050
Electronic Edition (link) BibTeX
Aravind Srinivasan, Chung-Piaw Teo:
A Constant-Factor Approximation Algorithm for Packet Routing and Balancing Local vs. Global Criteria. 2051-2068
Electronic Edition (link) BibTeX
Chengbin Chu, Rémy La:
Variable-Sized Bin Packing: Tight Absolute Worst-Case Performance Ratios for Four Approximation Algorithms. 2069-2083
Electronic Edition (link) BibTeX
Grazyna Mirkowska, Andrzej Salwicki, Marian Srebrny, Andrzej Tarlecki:
First-Order Specifications of Programmable Data Types. 2084-2096
Electronic Edition (link) BibTeX