Online Public Access Catalogue (OPAC)
Library,Documentation and Information Science Division

“A research journal serves that narrow

borderland which separates the known from the unknown”

-P.C.Mahalanobis


Image from Google Jackets

Boolean function complexity : advances and frontiers / Stasys Jukna.

By: Material type: TextTextSeries: Publication details: Berlin ; Springer-Verlag, 2012.Description: xv, 615 p. : ill. ; 24 cmISBN:
  • 9783642245077 (hbk.)
Subject(s): DDC classification:
  • 23 J93 511.352
Contents:
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.
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.
Tags from this library: No tags from this library for this title. Log in to add tags.
Holdings
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
Total holds: 0

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.

to post a comment.
Library, Documentation and Information Science Division, Indian Statistical Institute, 203 B T Road, Kolkata 700108, INDIA
Phone no. 91-33-2575 2100, Fax no. 91-33-2578 1412, ksatpathy@isical.ac.in