## Volume 384,
Number 1,
September 2007

Theory and Applications of Models of Computation
- S. Barry Cooper, Angsheng Li:

**Preface: Theory and applications of models of computation.
**1

- Jan Arpe, Rüdiger Reischuk:

**Learning juntas in the presence of noise.
**2-21

- Jin-yi Cai, Vinay Choudhary:

**Valiant's Holant Theorem and matchgate tensors.
**22-32

- Marcus Hutter:

**On universal prediction and Bayesian confirmation.
**33-48

- Sanjay Jain, Jochen Nessel, Frank Stephan:

**Invertible classes.
**49-65

- Lisa Hellerstein, Rocco A. Servedio:

**On PAC learning algorithms for rich Boolean function classes.
**66-76

- Andrej Muchnik, Alexander Shen, Mikhail Ustinov, Nikolai K. Vereshchagin, Michael V. Vyugin:

**Non-reducible descriptions for conditional Kolmogorov complexity.
**77-86

- Xiaoming Sun:

**Block sensitivity of weakly symmetric functions.
**87-91

- Xuehou Tan:

**A linear-time 2-approximation algorithm for the watchman route problem for simple polygons.
**92-103

- Alasdair Urquhart:

**Width versus size in resolution proofs.
**104-110

- Mingji Xia, Peng Zhang, Wenbo Zhao:

**Computational complexity of counting problems on 3-regular planar graphs.
**111-125

- Peng Zhang:

**A new approximation algorithm for the k-facility location problem.
**126-135

## Volume 384,
Numbers 2-3,
October 2007

Structural Information and Communication Complexity (SIROCCO 2005)
- Andrzej Pelc, David Peleg, Michel Raynal:

**Preface.
**137-138

- Jean-Claude Bermond, Laurent Braud, David Coudert:

**Traffic grooming on the path.
**139-151

- Ioannis Caragiannis, Aleksei V. Fishkin, Christos Kaklamanis, Evi Papaioannou:

**A tight bound for online colouring of disk graphs.
**152-160

- Andrea E. F. Clementi, Miriam Di Ianni, Massimo Lauria, Angelo Monti, Gianluca Rossi, Riccardo Silvestri:
On the bounded-hop MST problem on random Euclidean instances.
161-167
- Yefim Dinitz, Noam Solomon:

**Two absolute bounds for distributed bit complexity.
**168-183

- Markus Hinkelmann, Andreas Jakoby:

**Communications in unknown networks: Preserving the secret of topology.
**184-200

- Ralf Klasing, Euripides Markou, Tomasz Radzik, Fabiano Sarracco:

**Hardness and approximation results for Black Hole Search in arbitrary networks.
**201-221

- Giuseppe Prencipe:

**Impossibility of gathering by a set of autonomous mobile robots.
**222-231

- Nicola Santoro, Peter Widmayer:

**Agreement in synchronous networks with ubiquitous faults.
**232-249

- Mordechai Shalom, Shmuel Zaks:

**Minimization of the number of ADMs in SONET rings with maximum throughput with implications to the traffic grooming problem.
**250-262

- Rui Wang, Francis C. M. Lau:

**Optimal gossiping in square 2D meshes.
**263-286

Copyright © Fri Mar 12 17:33:13 2010
by Michael Ley (ley@uni-trier.de)