When Goethe revisited his work “IPHIGENIE AUF TAURIS” eight years after its initial publication, he expressed a sentiment (perhaps with a touch of resignation, excuse, or explanation) that a work is never truly finished; one must declare it complete when constraints of time and circumstances allow. This sentiment resonates with my experience while working on a book in the ever-evolving field of the complexity of Boolean functions. It is a delicate balance between capturing the multitude of significant new results and the constant influx of new findings.
In this monograph, I strive to depict the current state of research, encompassing the classical circuit model and complexity parameters such as circuit size and depth, forming the foundation for sequential and parallel computations. The exploration extends to various models, including monotone circuits, Boolean formulas, synchronous circuits, probabilistic circuits, programmable (universal) circuits, bounded-depth circuits, parallel random-access machines, and branching programs. The book delves into relationships between complexity parameters and models, as well as their connections to complexity theory and uniform computation models.
Designed for use in lectures and seminars, the book incorporates a wealth of new findings and numerous exercises for practical application of acquired methods. It stands as a self-contained resource, requiring only basic knowledge of computer science and mathematics.
Download
See also
- Software Exorcism: A Handbook for Debugging and Optimizing Legacy Code by Bill Blunden (2003)
- Hormones and the Endocrine System: Textbook of Endocrinology by Bernhard Kleine (2016)
- Genetics: A Conceptual Approach 6e by Benjamin A. Pierce (2017)
- A Functional Approach to Java by Ben Weidig (2022)
- Calculus of variations and optimal control by Amol Sasan (2005)