Издательство Springer, 2011, -633 pp.
Boolean circuit complexity is the combinatorics of computer science and involves many intriguing problems that are easy to state and explain, even for the layman. This book is a comprehensive description of basic lower bound arguments, covering many of the gems of this complexity Waterloo that have been discovered over the past several decades, right up to results from the last year or two. Many open problems, marked as Research Problems, are mentioned along the way. The problems are mainly of combinatorial flavor but their solutions could have great consequences in circuit complexity and computer science. The book will be of interest to graduate students and researchers in the fields of computer science and discrete mathematics. .
Computational complexity theory is the study of the inherent hardness or easiness of computational tasks. Research in this theory has two main strands. One of these strands—structural complexity—deals with high-level complexity questions: is space a more powerful resource than time? Does randomness enhance the power of efficient computation? Is it easier to verify a proof than to construct one? So far we do not know the answers to any of these questions; thus most results in structural complexity are conditional results that rely on various unproven assumptions, like P?NP.
The second strand—concrete complexity or circuit complexity—deals with establishing lower bounds on the computational complexity of specific problems, like multiplication of matrices or detecting large cliques in graphs. This is essentially a low-level study of computation; it typically centers around particular models of computation such as decision trees, branching programs, Boolean formulas, various classes of Boolean circuits, communication proto- cols, proof systems and the like. This line of research aims to establish unconditional lower bounds, which rely on no unproven assumptions.
This book is about the life on the second strand—circuit complexity— with a special focus on lower bounds. It gives self-contained proofs of a wide range of unconditional lower bounds for important models of computation, covering many of the gems of the field that have been discovered over the past several decades, right up to results from the last year or two. More than twenty years have passed since the well-known books on circuit complexity by Savage (1976), Nigmatullin (1983), Wegener (1987) and Dunne (1988) as well as a famous survey paper of Boppana and Sipser (1990) were written. I feel it is time to summarize the new developments in circuit complexity during these two decades.
The book is mainly devoted to mathematicians wishing to get an idea on what is actually going on in this one of the hardest, but also mathematically cleanest fields of computer science, to researchers in computer science wishing to refresh their knowledge about the state of art in circuit complexity, as well as to students wishing to try their luck in circuit complexity.
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.
Depth-three 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 Plane Proofs.
Epilogue.
A Mathematical Background.
Boolean circuit complexity is the combinatorics of computer science and involves many intriguing problems that are easy to state and explain, even for the layman. This book is a comprehensive description of basic lower bound arguments, covering many of the gems of this complexity Waterloo that have been discovered over the past several decades, right up to results from the last year or two. Many open problems, marked as Research Problems, are mentioned along the way. The problems are mainly of combinatorial flavor but their solutions could have great consequences in circuit complexity and computer science. The book will be of interest to graduate students and researchers in the fields of computer science and discrete mathematics. .
Computational complexity theory is the study of the inherent hardness or easiness of computational tasks. Research in this theory has two main strands. One of these strands—structural complexity—deals with high-level complexity questions: is space a more powerful resource than time? Does randomness enhance the power of efficient computation? Is it easier to verify a proof than to construct one? So far we do not know the answers to any of these questions; thus most results in structural complexity are conditional results that rely on various unproven assumptions, like P?NP.
The second strand—concrete complexity or circuit complexity—deals with establishing lower bounds on the computational complexity of specific problems, like multiplication of matrices or detecting large cliques in graphs. This is essentially a low-level study of computation; it typically centers around particular models of computation such as decision trees, branching programs, Boolean formulas, various classes of Boolean circuits, communication proto- cols, proof systems and the like. This line of research aims to establish unconditional lower bounds, which rely on no unproven assumptions.
This book is about the life on the second strand—circuit complexity— with a special focus on lower bounds. It gives self-contained proofs of a wide range of unconditional lower bounds for important models of computation, covering many of the gems of the field that have been discovered over the past several decades, right up to results from the last year or two. More than twenty years have passed since the well-known books on circuit complexity by Savage (1976), Nigmatullin (1983), Wegener (1987) and Dunne (1988) as well as a famous survey paper of Boppana and Sipser (1990) were written. I feel it is time to summarize the new developments in circuit complexity during these two decades.
The book is mainly devoted to mathematicians wishing to get an idea on what is actually going on in this one of the hardest, but also mathematically cleanest fields of computer science, to researchers in computer science wishing to refresh their knowledge about the state of art in circuit complexity, as well as to students wishing to try their luck in circuit complexity.
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.
Depth-three 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 Plane Proofs.
Epilogue.
A Mathematical Background.