This advanced textbook surveys research on boolean functions, circuits, parallel computation models, function algebras, and proof systems, with an overriding focus on the structure of "fast" parallel computation.

A survey of the present state of the art by internationally well-known authors Focus on "fast" parallel computation Includes numerous exercises ranging in difficulty Includes supplementary material: sn.pub/extras

Inhalt

1. Boolean Functions and Circuits.- 2. Circuit Lower Bounds.- 3. Circuit Upper Bounds.- 4. Randomness and Satisfiability.- 5. Propositional Proof Systems.- 6. Machine Models and Function Algebras.- 7. Higher Types.- References.