Polynomial bounds for VC dimension of sigmoidal neural networks. Bounding delays in packet-routing networks. Motion planning for a steering-constrained robot through moderate obstacles. Distinguishing tests for nondeterministic and probabilistic machines. Lower bounds for sorting networks.
Impossibility results for recycling random bits in two-prover proof systems.
Knowledge on the average-perfect, statistical and logarithmic. Explicit dispersers with polylog degree. More on the complexity of negation-limited circuits. On randomized one-round communication complexity. Bounding the power of preemption in randomized scheduling.