Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben

2012 | Buch

Our Adversary: The Circuit Kapitel lesen Erstes Kapitel lesen

Boolean Function Complexity

Advances and Frontiers

verfasst von: Stasys Jukna

Verlag: Springer Berlin Heidelberg

Buchreihe : Algorithms and Combinatorics

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

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.

Inhaltsverzeichnis

Frontmatter

The Basics

Frontmatter
Chapter 1. Our Adversary: The Circuit
Abstract
Boolean (or switching) functions map each sequence of bits to a single bit 0 or 1. Bit 0 is usually interpreted as “false”, and bit 1 as “true”. The simplest of such functions are the product\(\rm{x\cdot y}\), sum\(\rm{x\oplus y}\) mod 2, non-exclusive Or \({x\vee y}\), negation \(\neg x=1-x\) The central problem of boolean function complexity—the lower bounds problem—is:
Stasys Jukna
Chapter 2. Analysis of Boolean Functions
Abstract
We finish this introductory partwith some algebraic properties of boolean functions: their expression and approximation by polynomials. We will use these properties later to prove lower bounds for several circuit models. It is, however, convenient to have all these properties collected at one place. The impatient reader who wishes to begin proving lower bounds immediately may safely skip this section, and return later when the properties in question are used.
Stasys Jukna

Communication Complexity

Frontmatter
Chapter 3. Games on Relations
Abstract
The communication complexity of boolean functions is an information theoretic measure of their complexity. Besides its own importance, this measure is closely related to the computational complexity of functions: it corresponds to the smallest depth of circuits computing them. Thus, this measure can be used to prove circuit lower bounds. Communication complexity is appealing not only for its elegance and relation to circuit complexity, but also because its study involves the application of diverse tools from algebra, combinatorics and other fields of mathematics.
Stasys Jukna
Chapter 4. Games on 0-1 Matrices
Abstract
We have already seen that communication complexity of relations captures the depth of circuits. Protocols in this case are trying to solve search problems. In this chapter we consider the communication complexity of decision problems.
Stasys Jukna
Chapter 5. Multi-Party Games
Abstract
The rich mathematical theory of two-party communication naturally invites us to consider scenarios involving k > 2 players. In the simplest case, we have some function f(x)whose input x is decomposed into k equally-sized parts \(\rm x=\rm (x_{1},\,.\,.\,.\,,x_{k})\). There are k players who wish to collaboratively evaluate a given function f on every input x. Each player has unlimited computational power and full knowledge of the function. As in the case of two players, the players are not adversaries—they help and trust each other. Depending on what parts of the input x each player can see, there are two main models of communication:
Stasys Jukna

Circuit Complexity

Frontmatter
Chapter 6. Formulas
Abstract
Although for general non-monotone circuits no super-linear lower bounds are known, the situation for formulas is somewhat better: here we are able to prove quadratic and even super-quadratic lower bounds. These bounds are achieved using remarkably different arguments: counting, random restrictions, set covering and graph entropy.
Stasys Jukna
Chapter 7. Monotone Formulas
Abstract
We have seen that proving lower bound for general circuits is a very difficult task. Thus it is natural to try to obtain large lower bounds for a more restricted class of circuits, the class of monotone circuits. Monotone circuits consist only of AND and OR gates and have no NOT gates. Of course, such circuits cannot compute all boolean functions.
Stasys Jukna
Chapter 8. Span Programs
Abstract
In 1993 Karchmer and Wigderson introduced an interesting linear algebraic model for computing boolean functions—the span program. A span program is just a matrix over some field with rows labeled by literals. (In this chapter we will only work over the field GF(2), but the results hold for any field.) The span program accepts an input assignment if and only if the all-1 vector can be obtained as a linear combination of the rows whose labels are satisfied by the input. The size of the span program is the number of rows in the matrix. A span program is monotone if only positive literals are used as labels of the rows, that is, negated variables are not allowed.
Stasys Jukna
Chapter 9. Monotone Circuits
Abstract
We now consider monotone circuits, that is, circuits with fanin-2 AND and OR gates. As monotone formulas, such circuits can only compute monotone boolean functions.
Stasys Jukna
Chapter 10. The Mystery of Negations
Abstract
The main difficulty in proving nontrivial lower bounds on the size of circuits using AND, OR and NOT is the presence of NOT gates—we already know how to prove even exponential lower bounds for monotone functions if no NOT gates are allowed.
Stasys Jukna

Bounded Depth Circuits

Frontmatter
Chapter 11. Depth-3 Circuits
Abstract
We consider boolean circuits with unbounded-fanin AND and OR gates. Inputs are variables and their negations. Conjunctive and disjunctive normal forms are such circuits of depth two, and exponential lower bounds for them are easy to prove.
Stasys Jukna
Chapter 12. Large-Depth Circuits
Abstract
We now consider circuits of depth d ≥ 3. Out of attempts to prove lower bounds for such circuits, two powerful methods emerged. The first is a “depth reduction” argument: One tries to reduce the depth one layer at a time, until a circuit of depth 2 (or depth 1) remains. The key is the so-called Switching Lemma,which allows us to replace CNFs on the first two layers by DNFs, thus reducing the depth by 1.1
Stasys Jukna
Chapter 13. Circuits with Arbitrary Gates
Abstract
In this chapter we consider unbounded-fanin circuits with arbitrary boolean functions as gates. The size of such a circuit is defined as the total number of wires (rather than gates) it has.
Stasys Jukna

Branching Programs

Frontmatter
Chapter 14. Decision Trees
Abstract
A decision tree is an algorithm for computing a function of an unknown input. Each node of the tree is labeled by a variable and the branches from that node are labeled by the possible values of the variable. The leaves are labeled by the output of the function. The process starts at the root, knowing nothing, works down the tree, choosing to learn the values of some of the variables based on those already known and eventually reaches a decision. The decision tree complexity of a function is the minimum depth of a decision tree that computes that function.
Stasys Jukna
Chapter 15. General Branching Programs
Abstract
A branching program is a generalization of a decision tree where the underlying graph can be an arbitrary directed acyclic graph. The model of branching programs is one of the most fundamental sequential (in contrast to parallel, as circuits or formulas) model of computations. This model captures in a natural way the deterministic space whereas nondeterministic branching programs do the same for the nondeterministic mode of computation.
Stasys Jukna
Chapter 16. Bounded Replication
Abstract
Since, so far, we are unable to prove exponential lower bounds for general branching programs, it is natural to try to do this for restricted programs. We have seen that restricting the width of a program does not decrease their power too much: the resulting class of programs is almost as powerful at that of (unrestricted) formulas.
Stasys Jukna
Chapter 17. Bounded Time
Abstract
In this chapter we show a time-size tradeoff for nondeterministic branching programs. By the size of a program in this chapter we will mean the number of nodes, not just the number of labeled edges. A program computes a given function in time T if every accepted input has at least one accepting computation of length at most T.
Stasys Jukna

Fragments of Proof Complexity

Frontmatter
Chapter 18. Resolution
Abstract
Propositional proof systems operate with boolean formulas, the simplest of which are clauses, that is, ORs of literals, where each literal is either a variable \({x}_{i}\) or its negation \( \Gamma{x}_{i}\).A truth-assignment is an assignment of constants 0 and 1 to all the variables. Such an assignment satisfies (falsifies) a clause if it evaluates at least one (respectively, none) of its literals to 1.
Stasys Jukna
Chapter 19. Cutting Plane Proofs
Abstract
We now turn our attention to a proof system more powerful than resolution—the so-called cutting plane proof system. This proof system, which can be viewed as a “geometric generalization” of resolution, originated in works on integer programming by Gomory (1963) and Chvátal (1973); as a proof system it was first considered in Cook et al. (1987) The basic idea is to use a few elementary rules to prove that a given system of linear inequalities (or “cutting planes”) with integer coefficients does not have a 0-1 solution.
Stasys Jukna
Chapter 20. Epilogue
Abstract
The lower-bounds arguments we presented in this book work well for different restricted circuit classes but, so far, have not led to a non-linear lower bound for unrestricted circuits. In this concluding chapter we sketch several general results explaining this failure (the phenomenon of “natural proofs”) as well as showing a possible line of further attacks (the “fusion method”, indirect arguments).
Stasys Jukna
Backmatter
Metadaten
Titel
Boolean Function Complexity
verfasst von
Stasys Jukna
Copyright-Jahr
2012
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-24508-4
Print ISBN
978-3-642-24507-7
DOI
https://doi.org/10.1007/978-3-642-24508-4

Premium Partner

    Bildnachweise