Theoretical Computer Science, Volume 235

Volume 235, Number 1, 17 March 2000

• Eric Bach, Marcos A. Kiwi:
  Threshold data structures and coding theory. 3-23
  
• Avrim Blum, Goran Konjevod, R. Ravi, Santosh Vempala:
  Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems. 25-42
  
• Joan Boyar, René Peralta, Denis Pochuev:
  On the multiplicative complexity of Boolean functions over the basis (cap, +, 1). 43-57
  
• Harry Buhrman, Tao Jiang, Ming Li, Paul M. B. Vitányi:
  New applications of the incompressibility method: Part II. 59-70
  
• Peter Bürgisser:
  Cook's versus Valiant's hypothesis. 71-88
  
• Bruno Codenotti, Pavel Pudlák, Giovanni Resta:
  Some structural properties of low-rank matrices related to computational complexity. 89-107
  
• Jeff Edmonds:
  Scheduling in the dark. 109-141
  
• Leonid A. Levin:
  Self-stabilization of circular arrays of automata. 143-144
  
• J. Maurice Rojas:
  Uncomputably large integral points on algebraic plane curves? 145-162
  
• Joseph H. Silverman:
  On the distribution of integer points on curves of genus zero. 163-170
  
• Fangmin Song, YongSen Xu, Yuechen Qian:
  The self-reduction in lambda calculus. 171-181
  
• A. N. Trahtman:
  Algorithms finding the order of local testability of deterministic finite automaton and estimations of the order. 183-204
  
• Vijay V. Vazirani:
  Recent results on approximating the Steiner tree problem and its generalizations. 205-216
  

Volume 235, Number 2, 28 March 2000

• Hiroshi Era, Kenjiro Ogawa, Morimasa Tsuchiya:
  On upper bound graphs with respect to operations on graphs. 219-223
  
• Masahiro Hachimori:
  Constructible complexes and recursive division of posets. 225-237
  
• Kenji Kashiwabara:
  Extremality of submodular functions. 239-256
  
• Toru Kojima, Kiyoshi Ando:
  Wide-diameter and minimum length of fan. 257-266
  
• Hiroshi Maehara:
  Can a convex polyhedron have a developable face-cycle? 267-270
  
• Tomoki Nakamigawa:
  A generalization of diagonal flips in a convex polygon. 271-282
  
• Michio Ozeki:
  On covering radii and coset weight distributions of extremal binary self-dual codes of length 40. 283-308
  
• Tadashi Sakuma:
  Forced color classes, intersection graphs and the strong perfect graph conjecture. 309-324
  
• Kokichi Sugihara:
  Three-dimensional convex hull as a fruitful source of diagrams. 325-337
  
• Akihisa Tamura:
  Perfect (0, ±1)-matrices and perfect bidirected graphs. 339-356