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
Last update Fri May 24 20:53:25 2013
CET by the DBLP Team — 
Data released under the ODC-BY 1.0 license — See also our legal information page
