JCSS, Volume 65

Volume 65, Number 1, August 2002

• Lenore Cowen, Ronald Fagin, Joe Kilian, Jon M. Kleinberg:
  Guest Editor's Foreword. 1
  Electronic Edition (link) BibTeX
• Miklós Ajtai:
  Determinism versus Nondeterminism for Linear Time RAMs with Memory Restrictions. 2-37
  Electronic Edition (link) BibTeX
• Paul Beame, Faith E. Fich:
  Optimal Bounds for the Predecessor Problem and Related Problems. 38-72
  Electronic Edition (link) BibTeX
• Ming Li, Bin Ma, Lusheng Wang:
  Finding Similar Regions in Many Sequences. 73-96
  Electronic Edition (link) BibTeX
• Ran Raz, Omer Reingold, Salil P. Vadhan:
  Extracting all the Randomness and Reducing the Error in Trevisan's Extractors. 97-128
  Electronic Edition (link) BibTeX
• Moses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys:
  A Constant-Factor Approximation Algorithm for the k-Median Problem. 129-149
  Electronic Edition (link) BibTeX
• Valerie King, Garry Sagert:
  A Fully Dynamic Algorithm for Maintaining the Transitive Closure. 150-167
  Electronic Edition (link) BibTeX

Volume 65, Number 2, September 2002

• Charles A. Stewart:
  Reducibility between Classes of Port Graph Grammar. 169-223
  Electronic Edition (link) BibTeX
• Atsuyoshi Nakamura, Naoki Abe:
  Online Learning of Binary and n-ary Relations over Clustered Domains. 224-256
  Electronic Edition (link) BibTeX
• Vikraman Arvind, Johannes Köbler:
  New Lowness Results for ZPPNP and Other Complexity Classes. 257-277
  Electronic Edition (link) BibTeX
• Tero Harju, Oscar H. Ibarra, Juhani Karhumäki, Arto Salomaa:
  Some Decision Problems Concerning Semilinearity and Commutation. 278-294
  Electronic Edition (link) BibTeX
• Dan E. Willard:
  An Algorithm for Handling Many Relational Calculus Queries Efficiently. 295-331
  Electronic Edition (link) BibTeX
• Piotr Berman, Marek Karpinski, Lawrence L. Larmore, Wojciech Plandowski, Wojciech Rytter:
  On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts. 332-350
  Electronic Edition (link) BibTeX
• Konstantin Skodinis, Egon Wanke:
  Node Replacements in Embedding Normal Form. 351-376
  Electronic Edition (link) BibTeX
• Juha Honkala:
  The Equivalence Problem for DF0L Languages and Power Series. 377-392
  Electronic Edition (link) BibTeX
• Giovanni Pighizzini, Jeffrey Shallit, Ming-wei Wang:
  Unary Context-Free Grammars and Pushdown Automata, Descriptional Complexity and Auxiliary Space Lower Bounds. 393-414
  Electronic Edition (link) BibTeX
• Llew Mason, Peter L. Bartlett, Mostefa Golea:
  Generalization Error of Combined Classifiers. 415-438
  Electronic Edition (link) BibTeX

Volume 65, Number 3, November 2002

• Ming Li, Pavel A. Pevzner, Ron Shamir:
  Foreword. 441
  Electronic Edition (link) BibTeX
• Nadia El-Mabrouk:
  Reconstructing an ancestral genome using minimum segments duplications and reversals. 442-464
  Electronic Edition (link) BibTeX
• Guo-Hui Lin, Zhi-Zhong Chen, Tao Jiang, Jianjun Wen:
  The longest common subsequence problem for sequences with nested arc annotations. 465-480
  Electronic Edition (link) BibTeX
• Jens Lagergren:
  Combining polynomial running time and fast convergence for the disk-covering method. 481-493
  Electronic Edition (link) BibTeX
• Deep Jaitly, Paul E. Kearney, Guo-Hui Lin, Bin Ma:
  Methods for reconstructing the history of tandem repeats and their application to the human genome. 494-507
  Electronic Edition (link) BibTeX
• Bernard M. E. Moret, Jijun Tang, Li-San Wang, Tandy Warnow:
  Steps toward accurate reconstructions of phylogenies from gene-order data. 508-525
  Electronic Edition (link) BibTeX
• Gopal Pandurangan, Ramesh Hariharan:
  The restriction mapping problem revisited. 526-544
  Electronic Edition (link) BibTeX
• Rune B. Lyngsø, Christian N. S. Pedersen:
  The consensus string problem and the complexity of comparing hidden Markov models. 545-569
  Electronic Edition (link) BibTeX
• Yaw-Ling Lin, Tao Jiang, Kun-Mao Chao:
  Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis. 570-586
  Electronic Edition (link) BibTeX
• Glenn Tesler:
  Efficient algorithms for multichromosomal genome rearrangements. 587-609
  Electronic Edition (link) BibTeX

Volume 65, Number 4, December 2002

• Madhu Sudan:
  Foreword. 611
  Electronic Edition (link) BibTeX
• Jürgen Forster:
  A linear lower bound on the unbounded error probabilistic communication complexity. 612-625
  Electronic Edition (link) BibTeX
• Albert Atserias, Nicola Galesi, Pavel Pudlák:
  Monotone simulations of non-monotone proofs. 626-638
  Electronic Edition (link) BibTeX
• Amir Shpilka:
  Affine projections of symmetric polynomials. 639-659
  Electronic Edition (link) BibTeX
• Elchanan Mossel, Christopher Umans:
  On the complexity of approximating the VC dimension. 660-671
  Electronic Edition (link) BibTeX
• Russell Impagliazzo, Valentine Kabanets, Avi Wigderson:
  In search of an easy witness: exponential time vs. probabilistic polynomial time. 672-694
  Electronic Edition (link) BibTeX
• William Hesse, Eric Allender, David A. Mix Barrington:
  Uniform constant-depth threshold circuits for division and iterated multiplication. 695-716
  Electronic Edition (link) BibTeX
• Michal Koucký:
  Universal traversal sequences with backtracking. 717-726
  Electronic Edition (link) BibTeX