This free book presents a large number of recent research results previously unavailable in book form. Initially deals with the wee-known computation models, and goes on to special types of circuits, parallel computers, and branching programs. Includes basic theory as well recent research findings. Each chapter includes exercises.

**Description**

Research on the complexity of Boolean functions in non-uniform computation models is now part of one of the most interesting and important areas in theoretical computer science. It has a direct relevance to practical problems in the computer aided design of digital circuits. In this book Professor Dr. Wegener presents a large number of recent research results for the first time.

**Contents**

- Introduction to the theory of Boolean functions and circuits
- The minimization of Boolean functions
- The design of efficient circuits for some fundamental functions
- Asymptotic results and universal circuits
- Lower bounds on circuit complexity
- Relations between circuit size, formula size, and depth
- Formula size
- Circuits and other non uniform computation methods vs. Turing machines and other uniform computation models
- Hierarchie, mass production and reductions
- Bounded-depth circuits
- Synchronous, planar, and probabilistic circuits
- PRAMs and WRAMs: Parallel random access machines
- Pranching Programs

**Book Details**