Theoretical Computer Science, Volume 348

Volume 348, Number 1, 2 December 2005

• Hiroki Arimura, Sanjay Jain:
  Preface. 1-2
  
• Osamu Watanabe:
  Sequential sampling techniques for algorithmic learning theory. 3-14
  
• Steffen Lange, Gunter Grieser, Thomas Zeugmann:
  Inductive inference of approximations for recursive concepts. 15-40
  
• Jochen Nessel, Steffen Lange:
  Learning erasing pattern languages with queries. 41-57
  
• Ken Satoh:
  Learning taxonomic relation by case-based reasoning. 58-69
  
• François Denis, Rémi Gilleron, Fabien Letouzey:
  Learning from positive and unlabeled examples. 70-83
  
• Kouichi Hirata:
  Prediction-hardness of acyclic conjunctive queries. 84-94
  
• Bhaskar DasGupta, Barbara Hammer:
  On approximate learning by multi-layered feedforward circuits. 95-127
  

Volume 348, Numbers 2-3, 8 December 2005

• Josep Díaz, Juhani Karhumäki:
  Preface. 129
  
• Olivier Bournez, Emmanuel Hainry:
  Elementarily computable functions over the real numbers and R-sub-recursive functions. 130-147
  
• Andrei A. Bulatov, Martin Grohe:
  The complexity of partition functions. 148-186
  
• Zdenek Dvorak, Daniel Král, Ondrej Pangrác:
  Locally consistent constraint satisfaction problems. 187-206
  
• Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, Jian Zhang:
  On graph problems in a semi-streaming model. 207-216
  
• Lisa Fleischer:
  Linear tolls suffice: New bounds and algorithms for tolls in single source networks. 217-225
  
• Dimitris Fotakis, Spyros C. Kontogiannis, Paul G. Spirakis:
  Selfish unsplittable flows. 226-239
  
• Eran Halperin, Richard M. Karp:
  The minimum-entropy set cover problem. 240-250
  
• Shlomo Hoory, Avner Magen, Steven Myers, Charles Rackoff:
  Simple permutations mix well. 251-261
  
• Robert Krauthgamer, James R. Lee:
  The black-box complexity of nearest-neighbor search. 262-276
  
• Michal Kunc:
  Regular solutions of language inequalities and well quasi-orders. 277-293
  
• Emmanuelle Lebhar, Nicolas Schabanel:
  Close to optimal decentralized routing in long-range contact networks. 294-310
  
• Dieter van Melkebeek, Ran Raz:
  A time lower bound for satisfiability. 311-320
  
• Michael Soltys:
  LA, permutations, and the Hajós Calculus. 321-333
  
• Sergei Vassilvitskii, Mihalis Yannakakis:
  Efficiently computing succinct trade-off curves. 334-356
  
• Ryan Williams:
  A new algorithm for optimal 2-constraint satisfaction and its implications. 357-365