Six of the 28 papers chosen for presentation and publication were also chosen for the joint STOC/Complexity session, and so are presented in full in that proceedings and only by abstracts here. Only abstracts and references are provided for the two invited talks as well. Among the topics of the full papers are a lower bound for primality, computing from partial solutions, the complexity of solving equations over finite groups, the expected size of Heilbronn's triangles, quantum branded query complexity, deterministic amplification of space-bounded probabilistic undirected graph connectivity, the shortest lattice vector problem, and complicated complementations. No subject index. Annotation copyrighted by Book News, Inc., Portland, OR. |