Boolean function complexity : advances and frontiers
by Stasys Jukna
Bok Engelsk 2012 · Electronic books.
| Annen tittel | |
|---|---|
| Utgitt | Berlin : Springer , 2012
|
| Omfang | xv, 617 s.
|
| Opplysninger | Description based upon print version of record.. - ""Boolean Function Complexity ""; ""Preface""; ""Contents""; ""Part I The Basics""; ""Chapter 1: Our Adversary: The Circuit""; ""1.1 Boolean Functions""; ""1.2 Circuits""; ""1.3 Branching Programs""; ""1.4 Almost All Functions are Complex""; ""1.4.1 Circuits""; ""1.4.2 Approximation Complexity""; ""1.4.3 The Circuit Hierarchy Theorem""; ""1.4.4 Switching Networks and Formulas""; ""1.4.5 Invariant Classes""; ""1.5 So Where are the Complex Functions?""; ""1.5.1 On Explicitness""; ""1.5.2 Explicit Lower Bounds""; ""1.6 A 3n Lower Bound for Circuits""; ""1.7 Graph Complexity"". - ""1.7.1 Clique Complexity of Graphs""""1.7.2 Star Complexity of Graphs""; ""1.8 A Constant Factor Away From P â?  NP?""; ""Exercises""; ""Chapter 2: Analysis of Boolean Functions""; ""2.1 Boolean Functions as Polynomials""; ""2.2 Real Degree of Boolean Functions""; ""2.3 The Fourier Transform""; ""2.4 Boolean 0/1 Versus Fourier 1 Representation""; ""2.5 Approximating the Values 0 and 1""; ""2.6 Approximation by Low-Degree Polynomials""; ""2.7 Sign-Approximation""; ""2.8 Sensitivity and Influences""; ""Exercises""; ""Part II Communication Complexity""; ""Chapter 3: Games on Relations"". - ""3.1 Communication Protocols and Rectangles""""3.2 Protocols and Tiling""; ""3.3 Games and Circuit Depth""; ""3.3.1 Monotone Depth""; ""Exercises""; ""Chapter 4: Games on 0-1 Matrices""; ""4.1 Deterministic Communication""; ""4.2 Nondeterministic Communication""; ""4.2.1 Greedy Bounds""; ""4.2.2 Fooling-Set Bounds""; ""4.3 P = NP â?© co-NP for Fixed-Partition Games""; ""4.4 Clique vs. Independent Set Game""; ""4.5 Communication and Rank""; ""4.6 The Log-Rank Conjecture""; ""4.6.1 Known Gaps""; ""4.6.2 Small Rank Implies Large Discrepancy""; ""4.6.3 Rank and Chromatic Number"". - ""4.7 Communication with Restricted Advice""""4.8 PNPco-NP for Best-Partition Games""; ""4.9 Randomized Communication""; ""4.9.1 Distributional Complexity""; ""4.10 Lower Bound for the Disjointness Function""; ""4.11 Unbounded Error Communication and Sign-Rank""; ""4.12 Private vs. Public Randomness""; ""Exercises""; ""Chapter 5: Multi-Party Games""; ""5.1 The ``Number-in-Hand'' Model""; ""5.2 The Approximate Set Packing Problem""; ""5.3 Application: Streaming Algorithms""; ""5.4 The ``Number-on-Forehead'' Model""; ""5.5 The Discrepancy Bound""; ""5.6 Generalized Inner Product"". - ""5.7 Matrix Multiplication""""5.8 Best-Partition k-Party Communication""; ""Exercises""; ""Part III Circuit Complexity""; ""Chapter 6: Formulas""; ""6.1 Size Versus Depth""; ""6.2 A Quadratic Lower Bound for Universal Functions""; ""6.3 The Effect of Random Restrictions""; ""6.4 A Cubic Lower Bound""; ""6.5 Nechiporuk's Theorem""; ""6.6 Lower Bounds for Symmetric Functions""; ""6.7 Formulas and Rectangles""; ""6.8 Khrapchenko's Theorem""; ""6.9 Complexity is not Convex""; ""6.10 Complexity is not Submodular""; ""6.11 The Drag-Along Principle""; ""6.12 Bounds Based on Graph Measures"". - ""6.13 Lower Bounds via Graph Entropy"". - 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.
|
| Emner | |
| Sjanger | |
| Dewey | |
| ISBN | 3642245072. - 9783642245077
|
