Theoretical Computer Science, Volume 329

Volume 329, Number 1-3, December 2004

• Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich:
  Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2k-SAT. 1-45
  
• Michael Drmota:
  On Robson's convergence and boundedness conjectures concerning the height of binary search trees. 47-70
  
• Hana Chockler, Orna Kupferman:
  w-Regular languages are testable with a constant number of queries. 71-92
  
• Peter Jonsson, Andrei A. Krokhin:
  Recognizing frozen variables in constraint satisfaction problems. 93-113
  
• Tamás Hornung, Sándor Vágvölgyi:
  Storage-to-tree transducers with look-ahead. 115-158
  
• Thomas Strahm:
  A proof-theoretic characterization of the basic feasible functionals. 159-176
  
• Francine Blanchet-Sadri:
  Codes, orderings, and partial words. 177-202
  
• Yasuhiro Tajima, Etsuji Tomita, Mitsuo Wakatsuki, Matsuaki Terada:
  Polynomial time learning of simple deterministic languages via queries and a representative sample. 203-221
  
• Alin Bostan, Éric Schost:
  On the complexities of multipoint evaluation and interpolation. 223-235
  
• Gembu Morohashi, Shigeki Iwata:
  Some minimum merging networks. 237-250
  
• Jacques Peyriére, Bo Tan, Zhi-Xiong Wen, Jun Wu:
  The factor composition matrix of sequences. 251-269
  
• Leonid Kontorovich:
  Uniquely decodable n-gram embeddings. 271-284
  
• Grzegorz Malewicz:
  A tight analysis and near-optimal instances of the algorithm of Anderson and Woll. 285-301
  
• Tobias Brüggemann, Walter Kern:
  An improved deterministic local search algorithm for 3-SAT. 303-313
  
• Víctor Dalmau, Peter Jonsson:
  The complexity of counting homomorphisms seen from the other side. 315-323
  
• Lu Ruan, Hongwei Du, Xiaohua Jia, Weili Wu, Yingshu Li, Ker-I Ko:
  A greedy approximation for minimum connected dominating sets. 325-330
  
• Yuliang Zheng, Xian-Mo Zhang:
  The Generalized XOR Lemma. 331-337