Boolean function complexity. Advances and frontiers. (Q642463)

This monograph is about circuit complexity, dealing with establishing lower bounds on the computational complexity of specific problems, like particular models of computation such as Boolean formulas, various classes of Boolean circuits, decision trees, branching programs, communication protocols, proof systems. It gives self-contained proofs of a wide range of unconditional lower bounds for important models of computation, covering many topics of the field that have been discovered over the past several decades. More than 20 years have passed since the well-known books on circuit complexity by Savage (1976), Nigmatullin (1983), Wegener (1987), and Dunne (1988) as well as the survey paper of Boppana and Sipser (1990) were written. The aim of this new book is to summarize the new developments in circuit complexity during these two decades; it is mainly focused on classical circuit models (results on their randomized or algebraic versions receiving less attention here), and highlights some of the most important proof arguments for circuit lower bounds. The book consists of six parts: Part I: The basics (our adversary: the circuit; analysis of Boolean functions); Part II: Communication complexity (games on relations; games on 0-1 matrices; multi-party games); Part III: Circuit complexity (formulas; monotone formulas; span programs; monotone circuits; the mystery of negations); Part IV: Bounded depth circuits (depth-3 circuits; large-depth circuits; circuits with arbitrary gates); Part V: Branching programs (decision trees; general branching programs; bounded replication; bounded time); Part VI: Fragments of proof complexity (resolution; cutting planes proofs; epilogue). Moreover, there are an appendix (mathematical background), references and an index of notations. Each section ends with a collection of exercises. More than 40 open problems, marked as research problems, are mentioned along the way. Most of them are of a combinatorial or combinatorial-algebraic nature. The book is mainly devoted to mathematicians, to researchers in computer science wishing to complete their knowledge about the state of the art in circuit complexity, as well as to graduate students in mathematics and computer science, and is self-contained. The text assumes a certain mathematical maturity but no special knowledge in the theory of computing; the solutions of the problems in circuit complexity require a clever insight, rather than elaborated mathematical tools. It is an impressive work providing a large amount of information on circuit complexity.