search for books and compare prices
Tables of Contents for Introduction to Circuit Complexity
Chapter/Section Title
Page #
Page Count
Introduction
1
4
Complexity Measures and Reductions
5
30
An Example: Addition
5
2
Circuit Size and Depth
7
6
More Examples
13
5
Iterated Addition
13
3
Multiplication
16
1
Majority
16
1
Transitive Closure
16
2
Constant-Depth Reductions
18
8
Iterated Addition and Multiplication
20
1
Iterated Multiplication
21
3
Counting and Sorting
24
2
Asymptotic Complexity
26
5
A Lower Bound
26
2
An Upper Bound
28
3
Bibliographic Remarks
31
1
Exercises
32
3
Relations to Other Computation Models
35
44
Time on Turing Machines
36
5
Space on Turing Machines
41
1
Non-uniform Turing machines
42
4
Uniform Circuit Families
46
7
Alternating Turing Machines
53
7
Computation Model and Complexity Measures
53
3
Relations to Deterministic Complexity
56
1
An Example: Addition
57
1
Input Normal Form
58
2
Simultaneous Resource Bounds
60
7
Uniformity
60
3
Time and Space on Alternating Machines
63
4
Parallel Random Access Machines
67
7
Bibliographic Remarks
74
1
Exercises
75
4
Lower Bounds
79
28
The Elimination Method
80
4
A Lower Bound for the Threshold Function
80
1
A Lower Bound for the Parity Function
81
3
The Polynomial Method
84
5
Perceptrons and Polynomial Representations
84
2
Degree Lower Bounds
86
3
Lower Bounds for Constant-Depth Circuits
89
13
Depth Reduction for Constant-Depth Circuits
89
6
Approximating Circuits by Polynomials
95
1
Smolensky's Theorem
96
6
Bibliographic Remarks
102
2
Exercises
104
3
The NC Hierarchy
107
66
Bounded Fan-in Circuits
107
1
Unbounded Fan-in Circuits
108
2
Semi-Unbounded Fan-in Circuits
110
8
Polynomial Tree-size
111
2
Closure under Complementation
113
5
The Decomposability of the NC Hierarchy
118
4
Classes within NC1
122
27
Uniformity within NC1
122
4
A Hierarchy of Classes within NC1
126
1
Algebraic Characterizations
127
9
A Logical Characterization
136
13
P-Completeness
149
10
Reducibility Notions
149
3
Circuit Value Problems
152
2
Graph Problems
154
2
Problems from Logic, Algebra, and Language Theory
156
3
Overview of the Classes of the NC Hierarchy
159
1
Bibliographic Remarks
160
4
Exercises
164
9
Arithmetic Circuits
173
42
Complexity Measures and Reductions
173
5
Evaluating Arithmetic Circuits by Straight-Line Programs
178
3
Counting Problems in Boolean Circuits
181
25
Counting in SAC1
184
6
Counting in NC1
190
9
Counting in AC0
199
7
Relations among Arithmetic and Boolean Circuit Classes
206
2
Bibliographic Remarks
208
2
Exercises
210
5
Polynomial Time and Beyond
215
18
The class P/Poly
215
8
BPP and P/Poly
216
1
NP and P/Poly
217
3
Lower Bounds for P/Poly
220
2
Lower Bounds for Uniform Circuits
222
1
A Lower Bound for Uniform Threshold Circuits
223
5
Bibliographic Remarks
228
1
Exercises
229
4
Appendix: Mathematical Preliminaries
233
8
A1 Alphabets, Words, Languages
233
1
A2 Binary Encoding
233
1
A3 Asymptotic Behavior of Functions
234
1
A4 Turing Machines
234
2
A5 Logic
236
1
A6 Graphs
237
1
A7 Numbers and Functions
237
2
A8 Algebraic Structures
239
1
A9 Linear Algebra
239
2
Bibliography
241
14
List of Figures
255
2
Author Index
257
4
Subject Index
261