Boolean function complexity : advances and frontiers / Stasys Jukna.
Material type:
TextSeries: Publication details: Berlin ; Springer-Verlag, 2012.Description: xv, 615 p. : ill. ; 24 cmISBN: - 9783642245077 (hbk.)
- 23 J93 511.352
| Item type | Current library | Call number | Status | Date due | Barcode | Item holds | |
|---|---|---|---|---|---|---|---|
| Books | ISI Library, Kolkata | 511.352 J93 (Browse shelf(Opens below)) | Available | 135536 |
Browsing ISI Library, Kolkata shelves Close shelf browser (Hides shelf browser)
| No cover image available | ||||||||
| 511.35 St933(6) Recursive number theory : a development of recursive arithmetic in a logic-free equation calculus | 511.35 W757 Compution with recurrence relations | 511.352 Ar769 Computational complexity a modern approach | 511.352 J93 Boolean function complexity : | 511.352 K64 Causality, probability, and time / | 511.352 N676 Computability and randomness | 511.36 B611 Proof theory : |
Includes bibliographical references and index.
Part I Basics --
1. Our adversary: The circuit--
2. Analysis of Boolean functions--
Part II Communication Complexity --
3. Games on Relations--
4. Games on 0-1 Matrices--
5. Multi-Party games--
Part III Circuit Complexity --
6. Formulas--
7. Monotone Formulas--
8. Span Programs--
9. Monotone circuits--
10. The mystery of negations--
Part IV Bounded Depth Circuits --
11. Depth-3 Circuits--
12. Large-Depth circuits--
13. Circuits with arbitrary gates--
Part V Branching Programs --
14. Decision trees--
15. General branching programs--
16. Bounded replication--
17. Bounded time--
Part VI Fragments of Proof Complexity --
18. Resolution--
19. Cutting plane proofs--
20. Epilogue--
A Mathematical Background --
References --
Index.
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.
There are no comments on this title.
