Boolean Function Complexity: Advances and FrontiersBoolean 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. |
Other editions - View all
Common terms and phrases
ˇ ˇ adjacency matrix Alice Alice and Bob arbitrary assignment Ax Ä binary bipartite graph bits boolean circuits boolean matrix branching program circuit computing Claim clauses clique CNF formula co-NP columns communication complexity communication protocol computing f consider constant contains corresponding decision tree defined DeMorgan DeMorgan formula denote depth-2 circuit deterministic disjoint edges entries exists fanin function f graph G Hadamard matrix Hence Hint i-th implies independent set induction inequality input vector integer intersection labeled least Lemma Let f linear logn minterm monochromatic monomial monotone boolean function monotone circuit monotone function negation node obtain output pair parity function partition path players polynomial problem protocol prove random rank read-once rectangle resolution refutation restriction rows smallest number span program string subfunction submatrix subset Switching Lemma symmetric Theorem total number unsatisfiable upper bound vertex vertices