SIAM Journal on Computing, Volume 31

Volume 31, Number 1, 2001

• Jianer Chen, Antonio Miranda:
  A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling. 1-17
  
• Ming-Yang Kao, Tak Wah Lam, Wing-Kin Sung, Hing-Fung Ting:
  A Decomposition Theorem for Maximum Weight Bipartite Matchings. 18-26
  
• Ernst Althaus, Kurt Mehlhorn:
  Traveling Salesman-Based Curve Reconstruction in Polynomial Time. 27-66
  
• Pangfeng Liu, William Aiello, Sandeep N. Bhatt:
  Tree Search on an Atomic Model for Message Passing. 67-85
  
• Stefano Leonardi, Alberto Marchetti-Spaccamela, Alessio Presciutti, Adi Rosén:
  On-line Randomized Call Control Revisited . 86-112
  
• Jörg Flum, Martin Grohe:
  Fixed-Parameter Tractability, Definability, and Model-Checking. 113-145
  
• Chandra Chekuri, Rajeev Motwani, B. Natarajan, Clifford Stein:
  Approximation Techniques for Average Completion Time Scheduling. 146-166
  
• Michael Luby, Dana Randall, Alistair Sinclair:
  Markov Chain Algorithms for Planar Lattice Structures. 167-192
  
• Felipe Cucker, Dima Grigoriev:
  There are No Sparse NP_w-Hard Sets. 193-198
  
• Antonín Kucera, Theodore A. Slaman:
  Randomness and Recursive Enumerability. 199-211
  
• Vincent Bouchitté, Ioan Todinca:
  Treewidth and Minimum Fill-in: Grouping the Minimal Separators. 212-232
  
• Joan Boyar, Kim S. Larsen, Morten N. Nielsen:
  The Accommodating Function: A Generalization of the Competitive Ratio. 233-258
  
• Joe Sawada:
  Generating Bracelets in Constant Amortized Time. 259-268
  
• Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino:
  Disjunctions of Horn Theories and Their Cores. 269-288
  
• Pavol Hell, Ron Shamir, Roded Sharan:
  A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs. 289-305
  
• Miklós Csürös, Ming-Yang Kao:
  Provably Fast and Accurate Recovery of Evolutionary Trees through Harmonic Greedy Triplets. 306-322
  
• Jing Chao Chen:
  Proportion Extend Sort. 323-330
  

Volume 31, Number 2, 2001

• Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber:
  Approximating the Throughput of Multiple Machines in Real-Time Scheduling. 331-352
  
• Rasmus Pagh:
  Low Redundancy in Static Dictionaries with Constant Query Time. 353-363
  
• Monika Rauch Henzinger, Valerie King:
  Maintaining Minimum Spanning Forests in Dynamic Graphs. 364-374
  
• Mary Cryan, Leslie Ann Goldberg, Paul W. Goldberg:
  Evolutionary Trees Can be Learned in Polynomial Time in the Two-State General Markov Model. 375-397
  
• Salil P. Vadhan:
  The Complexity of Counting in Sparse, Regular, and Planar Graphs. 398-427
  
• Vojtech Rödl, Andrzej Rucinski, Michelle Wagner:
  Matchings Meeting Quotas and Their Impact on the Blow-Up Lemma. 428-446
  
• Gen-Huey Chen, Ming-Yang Kao, Yuh-Dauh Lyuu, Hsing-Kuo Wong:
  Optimal Buy-and-Hold Strategies for Financial Markets with Bounded Daily Returns. 447-459
  
• Vwani P. Roychowdhury, Farrokh Vatan:
  Quantum Formulas: A Lower Bound and Simulation. 460-476
  
• Joseph Naor, Leonid Zosin:
  A 2-Approximation Algorithm for the Directed Multiway Cut Problem. 477-482
  
• Wolfgang Merkle:
  The Global Power of Additional Queries to P-Random Oracles. 483-495
  
• Ketan Mulmuley, Milind A. Sohoni:
  Geometric Complexity Theory I: An Approach to the P vs. NP and Related Problems. 496-526
  
• Amotz Bar-Noy, Ari Freund, Joseph Naor:
  On-Line Load Balancing in a Hierarchical Server Topology. 527-549
  
• Funda Ergün, Ravi Kumar, Ronitt Rubinfeld:
  Checking Approximate Computations of Polynomials and Functional Equations. 550-576
  
• Frank Hoffmann, Christian Icking, Rolf Klein, Klaus Kriegel:
  The Polygon Exploration Problem. 577-600
  
• Ashim Garg, Roberto Tamassia:
  On the Computational Complexity of Upward and Rectilinear Planarity Testing. 601-625
  
• Frank Thomson Leighton, Chi-Jen Lu, Satish Rao, Aravind Srinivasan:
  New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning. 626-641
  
• Hagit Attiya, Arie Fouren:
  Adaptive and Efficient Algorithms for Lattice Agreement and Renaming. 642-664
  

Volume 31, Number 3, 2001

• Moses Charikar, Samir Khuller, Balaji Raghavachari:
  Algorithms for Capacitated Vehicle Routing. 665-682
  
• Conrado Martínez, Salvador Roura:
  Optimal Sampling Strategies in Quicksort and Quickselect. 683-705
  
• Cyril Gavoille, David Peleg:
  The Compactness of Interval Routing for Almost All Graphs. 706-721
  
• Amir M. Ben-Amram, Zvi Galil:
  Topological Lower Bounds on Algebraic Random Access Machines. 722-761
  
• J. Ian Munro, Venkatesh Raman:
  Succinct Representation of Balanced Parentheses and Static Trees. 762-776
  
• Denis Thérien, Thomas Wilke:
  Temporal Logic and Semidirect Products: An Effective Characterization of the Until Hierarchy. 777-798
  
• Cristopher Moore, Martin Nilsson:
  Parallel Quantum Computation and Quantum Codes. 799-815
  
• Eli Gafni, Michael Mitzenmacher:
  Analysis of Timing-Based Mutual Exclusion with Random Times. 816-837
  
• Joseph Y. Halpern, Yoram Moses, Orli Waarts:
  A Characterization of Eventual Byzantine Agreement. 838-865
  
• Amit Chakrabarti, Subhash Khot, Yaoyun Shi:
  Evasiveness of Subgraph Containment and Related Properties. 866-875
  
• Harry Buhrman, Luc Longpré:
  Compressibility and Resource Bounded Measure. 876-886
  
• Harry Buhrman, Lance Fortnow, Sophie Laplante:
  Resource-Bounded Kolmogorov Complexity Revisited. 887-905
  
• Aduri Pavan, Alan L. Selman:
  Separation of NP-Completeness Notions. 906-918
  
• Stavros G. Kolliopoulos, Clifford Stein:
  Approximation Algorithms for Single-Source Unsplittable Flow. 919-946
  
• Michele Boreale, Rocco De Nicola, Rosario Pugliese:
  Proof Techniques for Cryptographic Processes. 947-986
  
• J. H. Rieger:
  Corrigendum: Proximity in Arrangements of Algebraic Sets. 987
  

Volume 31, Number 4, 2002

• Yoram Moses, Sergio Rajsbaum:
  A Layered Analysis of Consensus. 989-1021
  
• Eduardo Sany Laber, Ruy Luiz Milidiú, Artur Alves Pessoa:
  On Binary Searching with Nonuniform Costs. 1022-1047
  
• Paul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks:
  The Efficiency of Resolution and Davis--Putnam Procedures. 1048-1075
  
• Christoph Dürr, Miklos Santha:
  A Decision Procedure for Unitary Linear Quantum Cellular Automata. 1076-1089
  
• Uriel Feige, Robert Krauthgamer:
  A Polylogarithmic Approximation of the Minimum Bisection. 1090-1118
  
• Wolfgang Merkle:
  Lattice Embeddings for Abstract Bounded Reducibilities. 1119-1155
  
• Alfons Geser:
  Decidability of Termination of Grid String Rewriting Rules. 1156-1168
  
• Rodney G. Downey, Denis R. Hirschfeldt, André Nies:
  Randomness, Computability, and Density. 1169-1183
  
• Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson:
  Space Complexity in Propositional Calculus. 1184-1211
  
• Thorsten Theobald:
  An Enumerative Geometry Framework for Algorithmic Line Problems in $\mathbb R^3$. 1212-1228
  
• Leslie G. Valiant:
  Quantum Circuits That Can Be Simulated Classically in Polynomial Time. 1229-1254
  
• Zhi-Zhong Chen, Xin He, Chun-Hsi Huang:
  Finding Double Euler Trails of Planar Graphs in Linear Time. 1255-1285
  
• Hagit Attiya, Sergio Rajsbaum:
  The Combinatorial Structure of Wait-Free Solvable Tasks. 1286-1313
  

Volume 31, Number 5, 2002

• Vasek Chvátal, Jean Fonlupt, L. Sun, A. Zemirline:
  Recognizing Dart-Free Perfect Graphs. 1315-1338
  
• Yunhong Zhou, Subhash Suri:
  Algorithms for a Minimum Volume Enclosing Simplex in Three Dimensions. 1339-1357
  
• Rocco A. Servedio:
  Perceptron, Winnow, and PAC Learning. 1358-1369
  
• Baruch Awerbuch, Yossi Azar, Stefano Leonardi, Oded Regev:
  Minimizing the Flow Time Without Migration. 1370-1382
  
• Moni Naor, Omer Reingold, Alon Rosen:
  Pseudorandom Functions and Factoring. 1383-1404
  
• Ralf Hiptmair, Jörg Ostrowski:
  Generators of $H_1(\Gamma_{h}, \mathbbZ)$ for Triangulated Surfaces: Construction and Classification. 1405-1423
  
• Anna Gál, Adi Rosén:
  A Theorem on Sensitivity and Applications in Private Computation. 1424-1437
  
• Francesco M. Malvestuto, Mauro Mezzini:
  A Linear Algorithm for Finding the Invariant Edges of an Edge-Weighted Graph. 1438-1455
  
• Alex Brodsky, Nicholas Pippenger:
  Characterizations of 1-Way Quantum Finite Automata. 1456-1478
  
• Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan:
  Fast Greedy Algorithms for Constructing Sparse Geometric Spanners. 1479-1500
  
• Adam Klivans, Dieter van Melkebeek:
  Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. 1501-1526
  
• Martin E. Dyer, Alan M. Frieze, Mark Jerrum:
  On Counting Independent Sets in Sparse Graphs. 1527-1541
  
• Dieter Spreen:
  Safe Weak Minimization Revisited. 1542-1556
  
• Ilan Newman:
  Testing Membership in Languages that Have Small Width Branching Programs. 1557-1570
  
• Alain J. Mayer, Rafail Ostrovsky, Yoram Ofek, Moti Yung:
  Self-Stabilizing Symmetry Breaking in Constant Space. 1571-1595
  
• Tomás Feder, Rajeev Motwani, Carlos S. Subi:
  Approximating the Longest Cycle Problem in Sparse Graphs. 1596-1607
  
• Eran Halperin:
  Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs. 1608-1623
  
• Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino:
  Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities. 1624-1643
  

Volume 31, Number 6, 2002

• Alexander Russell, Michael E. Saks, David Zuckerman:
  Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model. 1645-1662
  
• Venkatesan Guruswami, Johan Håstad, Madhu Sudan:
  Hardness of Approximate Hypergraph Coloring. 1663-1686
  
• Hsien-Kuei Hwang, Ralph Neininger:
  Phase Change of Limit Laws in the Quicksort Recurrence under Varying Toll Functions. 1687-1722
  
• Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh:
  Are Bitvectors Optimal? 1723-1744
  
• János Pach, Gábor Tardos:
  On the Boundary Complexity of the Union of Fat Triangles. 1745-1760
  
• Richard Cole, Ramesh Hariharan:
  Approximate String Matching: A Simpler Faster Algorithm. 1761-1782
  
• Jochen Könemann, R. Ravi:
  A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees. 1783-1793
  
• Mayur Datar, Aristides Gionis, Piotr Indyk, Rajeev Motwani:
  Maintaining Stream Statistics over Sliding Windows. 1794-1813
  
• Pankaj K. Agarwal, Therese C. Biedl, Sylvain Lazard, Steve Robbins, Subhash Suri, Sue Whitesides:
  Curvature-Constrained Shortest Paths in a Convex Polygon. 1814-1851
  
• Yijie Han, Xiaojun Shen:
  Parallel Integer Sorting Is More Efficient Than Parallel Comparison Sorting on Exclusive Write PRAMs. 1852-1878
  
• Seth Pettie, Vijaya Ramachandran:
  A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest. 1879-1895
  
• Martin Kutz:
  Lower Bounds for Lucas Chains. 1896-1908
  
• Nader H. Bshouty, Yishay Mansour:
  Simple Learning Algorithms for Decision Trees and Multivariate Polynomials. 1909-1925
  
• Hanno Lefmann, Niels Schmitt:
  A Deterministic Polynomial-Time Algorithm for Heilbronn's Problem in Three Dimensions. 1926-1947
  
• Edith Hemaspaandra, Gerd Wechsung:
  The Minimization Problem for Boolean Formulas. 1948-1958