Boolean function complexity : advances and frontiers
 Responsibility
 Stasys Jukna.
 Language
 English.
 Imprint
 Berlin ; New York : Springer, c2012.
 Physical description
 xv, 617 p. : ill ; 24 cm.
 Series
 Algorithms and combinatorics ; 27.
Access
Available online
 dx.doi.org SpringerLink
Math & Statistics Library

Stacks

Unknown
QA267.7 .J85 2012

Unknown
QA267.7 .J85 2012
More options
Creators/Contributors
 Author/Creator
 Jukna, Stasys, 1953
Contents/Summary
 Bibliography
 Includes bibliographical references (p. 591610) and index.
 Contents

 Part I Basics. Part II Communication Complexity. Part III Circuit Complexity. Part IV Bounded Depth Circuits. Part V Branching Programs. Part VI Fragments of Proof Complexity. A Epilog. B Mathematical Background. References. Index.
 (source: Nielsen Book Data)
 Publisher's Summary
 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.
(source: Nielsen Book Data)
Subjects
Bibliographic information
 Publication date
 2012
 Series
 Algorithms and combinatorics ; 27
 ISBN
 9783642245077 (hbk.)
 3642245072 (hbk.)
 9783642245084 (ebk.)
 3642245080 (ebk.)