Ingo Wegener:

The Complexity of Boolean Functions

Original cover text
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. Initially he deals with the well known computation models (circuits and formulae), and he goes on to special types of circuits, parallel computers, and branching programs. Basic results are included as well as the most recent research results. The Complexity of Boolean Functions assumes a basic knowledge of computer science and mathematics. It deals with both efficient algorithms and lower bounds. At the end of each chapter there are exercises with varying levels of difficulty to help students using the book.

On this version of the Blue Book:
This version of The Complexity of Boolean Functions for some people simply the Blue Book due to the color of the cover of the original from 1987, is not a print-out of the original sources. It is rather a facsimile of the original monograph typeset in LaTeX.
The source files of the Blue Book which still exist (in 1999) have been written for an old version of troff and virtually cannot be printed out anymore. This is because of the strange standard font used for the text as well as the special fonts for math symbols seem to be nowhere to find today. Even if one could find a solution for the special symbols, the available text fonts yield a considerably different page layout which seems to be undesirable. Things are further complicated by the fact that the source files for the figures have been lost and would have to be redone with pic. Hence, it has been decided to translate the whole sources to LaTeX in order to be able to fix the above problems more easily. Of course, the result can still only be an approximation to the original. The fonts are those of the CM series of LaTeX and have different parameters than the original ones. For the spacing of equations, the standard mechanisms of LaTeX have been used, which are quite different from those of troff. Hence, it is nearly unavoidable that page breaks occur in different places than in the original book. Nevertheless, it has been made sure that all numbered items (theorems, equations) can be found on the same pages as in the original. You are encouraged to report typos and errors to Ingo Wegener

Download PDF-file of the entire book.

Contents:

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

Copyright (c) 1987, by John Wiley and Sons Ltd, and B. G. Teubner, Stuttgart. ISBN: 3-519-02107-2, Ingo Wegener

---

ISSN 1433-8092 | Imprint