JCSS, Volume 68

Volume 68, Number 1, February 2004

• Alexandru Mateescu, Arto Salomaa, Sheng Yu:
  Subword histories and Parikh matrices. 1-21
  
• Kwok Pui Choi, Louxin Zhang:
  Sensitivity analysis and efficient method for identifying optimal spaced seeds. 22-40
  
• Ngoc-Minh Lê:
  Abstract Voronoi diagram in 3-space. 41-79
  
• Luca Becchetti, Stefano Leonardi, S. Muthukrishnan:
  Average stretch without migration. 80-95
  
• Rodney G. Downey, Denis R. Hirschfeldt, Geoffrey LaForte:
  Randomness and reducibility. 96-114
  
• Deng-Feng Li:
  Some measures of dissimilarity in intuitionistic fuzzy structures. 115-122
  
• Emmanuelle Anceaume, Antonio Fernández, Achour Mostéfaoui, Gil Neiger, Michel Raynal:
  A necessary and sufficient condition for transforming limited accuracy failure detectors. 123-133
  
• Wolfgang Merkle, Frank Stephan:
  Trees and learning. 134-156
  
• James H. Anderson, Anand Srinivasan:
  Mixed Pfair/ERfair scheduling of asynchronous periodic tasks. 157-204
  
• Nader H. Bshouty, Jeffrey C. Jackson, Christino Tamon:
  More efficient PAC-learning of DNF with membership queries under the uniform distribution. 205-234
  

Volume 68, Number 2, March 2004

• Sampath Kannan, Mihalis Yannakakis:
  Guest Editors' foreword. 237
  
• Dimitris Achlioptas, Paul Beame, Michael S. O. Molloy:
  A sharp threshold in proof complexity yields lower bounds for satisfiability search. 238-268
  
• Bernard Chazelle, Ding Liu:
  Lower bounds for intersection searching and fractional cascading in higher dimension. 269-284
  
• Martin Grohe:
  Computing crossing numbers in quadratic time. 285-302
  
• Adam R. Klivans, Rocco A. Servedio:
  Learning DNF in time 2^Õ(n1/3). 303-318
  
• Marcus Schaefer, Daniel Stefankovic:
  Decidability of string graphs. 319-334
  
• John Dunagan, Santosh Vempala:
  Optimal outlier removal in high-dimensional spaces. 335-373
  
• Luca de Alfaro, Rupak Majumdar:
  Quantitative solution of omega-regular games. 374-397
  
• Andris Ambainis:
  A new protocol and lower bounds for quantum coin flipping. 398-416
  
• Moses Charikar, Rina Panigrahy:
  Clustering to minimize the sum of cluster diameters. 417-441
  
• Michel X. Goemans, David P. Williamson:
  Approximation algorithms for M_AX-3-C_UT and other problems via complex semidefinite programming. 442-470
  

Volume 68, Number 3, May 2004

• Narayan Vikas:
  Computational complexity of compaction to irreflexive cycles. 473-496
  
• Wojciech Palacz:
  Algebraic hierarchical graph transformation. 497-520
  
• Pirkko Kuusela, Daniel Ocone:
  Learning with side information: PAC learning bounds. 521-545
  
• Etienne Grandjean, Frédéric Olive:
  Graph properties checkable in linear time in the number of vertices. 546-597
  
• Hung-Min Sun, Bing-Chang Chen, Her-Tyan Yeh:
  On the design of time-stamped signatures. 598-610
  
• Frank Drewes, Joost Engelfriet:
  Branching synchronization grammars with nested tables. 611-656
  
• Christopher M. Homan:
  Tight lower bounds on the ambiguity of strong, total, associative, one-way functions. 657-674
  
• Pavol Duris, Juraj Hromkovic, Katsushi Inoue:
  On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata. 675-699
  

Volume 68, Number 4, June 2004

• Edith Cohen, Venkatesan Guruswami:
  Guest Editors' foreword. 701
  
• Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar:
  An information statistics approach to data stream and communication complexity. 702-732
  
• Jon Feldman, David R. Karger:
  Decoding turbo-like codes via linear programming. 733-752
  
• Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky:
  Testing juntas. 753-787
  
• Gianni Franceschini, Roberto Grossi, J. Ian Munro, Linda Pagli:
  Implicit B-trees: a new data structure for the dictionary problem. 788-807
  
• Adam R. Klivans, Ryan O'Donnell, Rocco A. Servedio:
  Learning intersections and thresholds of halfspaces. 808-840
  
• Santosh Vempala, Grant Wang:
  A spectral algorithm for learning mixture models. 841-860