## 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

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