Computational complexity theory sets the formal mathematical foundations of efficient computation, asking which tasks can be performed given the limitations of computational resources. The field has expanded to include mathematical disciplines, natural and physical sciences, and social sciences such as economics. This volume came from a Park City summer program through the Institute for Advanced Study, and covers its three weeks of lectures. Topics include complexity theory (the discipline from Godel to Feynman, average case complexity, exploring complexity through reductions, and quantum computation), lower bounds (circuit and communication complexity and proof complexity) and randomness in computation (pseudo-randomness and probabilistic proof systems). Presenters include bibliographies with their groups of lectures, but this volume does not include an index. Annotation ©2004 Book News, Inc., Portland, OR (booknews.com)