Title: Theory / Unimportant / CS / Fundamental / Complexity / Circuit - Vollmer
Tags: fromMath mathToDef mathToSee automaticImplies equivalentHand toBinaryRelation hasSeenConjDef

Name: ADD
Definition: \(\{0,1\}^{2n}\to\{0,1\}^{n+1}\). Takes two \(n\)-bits integer encodings, output their sum
Page: 5
Chapter: 1
Variables: \(n\in\mathbb N\)

Name: A boolean function
Definition: A function of the form \(f:\{0,1\}^m\to \{0,1\}\) for some \(m\in\mathbb N\).
Page: 7
Chapter: 1
Section: 2
Kind: Def

Name: A family of boolean function
Definition: A sequence \((f_m):\{0,1\}^m\to \{0,1\}\) for all \(m\in\mathbb N\).
Page: 7
Chapter: 1
Section: 2
Index: 3
Kind: Def

Name: A basis
Definition: A finite set of boolean functions and of family of boolean functions.
Page: 7
Chapter: 1
Section: 2
Index: 5
Kind: Def

Name: A Boolean circuit over \(B\)
Definition: \(C=(V,E,\alpha,\beta,\omega)\) where \((V,E)\) is a finite directed acyclicc graph, \(\alpha:E\to\mathbb N\) is an injective function, \(\beta:V\to B\cup\{x_1,\dots,x_n\}\) and \(\omega:V\to \{y_1,\dots,y_m,*\}\) such that:
-IF \(v\in V\) has in-degree 0, then \(\beta(v)\in\{x_1,\dots,x_n\}\) or \(\beta(v)\) is a \(0\)-ary Boolean function from \(B\)
-If \(v\in V\) has in-degree \(k>0\), then \(\beta(v)\) is a \(k\)-ary Boolean function from \(B\) or a family of Boolean function from \(B\)
-For every \(1\le i\le n\), there is at most one node \(v\in V\) such that \(\beta(v)=x_i\)
-For every \(1\le i\le m\) there is exactly one node \(v\in V\) such that \(\omega(v)=y_i\).
Page: 8
Chapter: 1
Section: 2
Variables: \(B\) a basis.
Index: 6
Kind: Def

Name: Gate
Definition: An element of \(V\).
Page: 8
Chapter: 1
Section: 2
Variables: \(B\) a basis
\(C=(V,E,\alpha,\beta,\omega)\) a circuit.
Index: 6
Kind: Def

Name: A wire
Definition: An element of \(E\).
Page: 8
Chapter: 1
Section: 2
Variables: \(B\) a basis, \(C=(V,E,\alpha,\beta,\omega)\) a circuit.
Kind: Def

Name: An input wire of \(u\)
Definition: A gate \((u,v)\in E\).
Page: 8
Chapter: 1
Section: 2
Variables: \(B\) a basis,
\(C=(V,E,\alpha,\beta,\omega)\) a circuit and
\(u\in V\).
Kind: Def

Name: A predecessor gate of \(v\)
Definition: A gate \(u\) such that \((u,v)\in E\)
Page: 8
Chapter: 1
Section: 2
Variables: \(B\) a basis, \(C=(V,E,\alpha,\beta,\omega)\) a circuit.
Kind: Def

Name: An input node
Definition: A node \(v\) such that \(\beta(v)=x_i\) for some \(i\).
Page: 8
Chapter: 1
Section: 2
Variables: \(B\) a basis, \(C=(V,E,\alpha,\beta,\omega)\) a circuit and \(v\in V\).
Kind: Def

Name: An output gate/node
Definition: A node \(v\) such that \(\omega(v)\ne *\).
Page: 8
Chapter: 1
Section: 2
Variables: \(B\) a basis, \(C=(V,E,\alpha,\beta,\omega)\) a circuit and \(v\in V\).
Kind: Def

Name: The type of the gate \(v\)
Page: 8
Chapter: 1
Section: 2
Variables: \(B\) a basis,
\(C=(V,E,\alpha,\beta,\omega)\) a circuit
\(v\in V\).
Notation: \(\beta(v)\)
Kind: Def

Q: [...] is defined as:
[...]
A: \(\text{val}_v(a_1,\dots,a_n)\); -\(a_i\) if \(\beta(v)=x_i\)
-\(\beta(v)(\text{val}_{v_1}(a_1,\dots,a_n),\dots,\text{val}_{v_k}(a_1,\dots,a_n)) \) where \(v_1,\dots,v_k\) are the \(k\) predecessors of \(v\) with \(\alpha(v_1)<\dots<\alpha(v_k)\)
Page: 8
Chapter: 1
Section: 2
Variables: \(B\) a basis, \(C=(V,E,\alpha,\beta,\omega)\) a circuit with \(n\) inputs and \(m\) outputs. Let \(a_1,\dots,a_n\in\{0,1\}\) and \(v\in V\).
Index: 7
Kind: Def

Name: The function computed by \(C\)
Definition: The function which associates to each \(a_1,\dots,a_n\in\{0,1\}\), \((\text{val}_{v_1}(a_1,\dots,a_n),\dots,\text{val}_{v_m}(a_1,\dots,a_n)) \) where the \(v_i\) is the gate such that \(\omega(v_i)=y_i\).
Page: 9
Chapter: 1
Section: 2
Variables: \(B\) a basis, \(C=(V,E,\alpha,\beta,\omega)\) a circuit over \(B\) with \(n\) inputs and \(m\) outputs.
Index: 7
Kind: Def

Name: Symmetric word function
Definition: A word function whose output only depends on the number of \(1\) of the input.
Page: 9
Chapter: 1
Section: 2
Variables: \(f:\{0,1\}^m\to \{0,1\}\).
Index: 5
Kind: Def

Name: the characteristic function of \(A\)
Definition: \(C=(V,E,\alpha,\beta,\omega)\) a circuit with \(n\) inputs and \(1\) output such that \(C\) output 1 on the input \(w\) iff \(w\in A\).
Page: 9
Chapter: 1
Section: 2
Variables: \(B\) a basis,
\(A\) a language of binary word
Kind: Def

Name: A circuit family over \(B\)
Definition: A sequence \(\mathbf C=(C_0,C_1,\dots)\) where for every \(n\in\mathbb N\), \(C_n\) is a circuit over \(B\) with \(n\) inputs.
Page: 10
Chapter: 1
Section: 2
Variables: \(B\) a basis.
Kind: Def

Name: The function computed by \(\mathbf C\)
Definition: The function \(f:\{0,1\}\to\{0,1\}^*\) such that \(f\) restricted to \(\{0,1\}^m\) is the function computed by the circuit \(C_m\).
Page: 10
Chapter: 1
Section: 2
Variables: \(B\) a basis. Let \(\mathbf C=(C_0,C_1,\dots)\) a circuit family over \(B\)
Kind: Def

Name: Language accepted by \(\mathbf C\)
Definition: The language of binary words \(w\) such that \(\mathbf C\), \(f(w)=1\).
Page: 10
Chapter: 1
Section: 2
Variables: \(B\) a basis. Let \(\mathbf C=(C_0,C_1,\dots)\) a circuit family over \(B\) computing a function \(f\)
Kind: Def

Name: The size of \(C\)
Definition: The number of non-input gates in \(V\).
Page: 10
Chapter: 1
Section: 2
Variables: \(B\) a basis,
\(C=(V,E,\alpha,\beta,\omega)\) a circuit over \(B\)
Notation: \(C(S)\)
Index: 11
Kind: Def
Extra: Notation page 26, 5.1 ?

Name: The depth of \(C\)
Definition: The length of the longest directed path in \((V,E)\).
Page: 10
Chapter: 1
Section: 2
Variables: \(B\) a basis,
\(C=(V,E,\alpha,\beta,\omega)\) a circuit over \(B\)
Index: 11
Kind: Def

Name: The depth of \(\mathbf C\)
Definition: The function associating \(i\in\mathbb N\) to the size of \(C_i\).
Page: 10
Chapter: 1
Section: 2
Variables: \(B\) a basis,
\(\mathbf C=(C_0,C_1,\dots)\) a circuit family over \(B\) computing a function \(f\)
Index: 11
Kind: Def

Name: The standard bounded fan-in basis
Definition: \(\{\neg,\land^2,\lor^2\}\)
Page: 10
Chapter: 1
Section: 2
Notation: \(B_0\)
Index: 12
Kind: Def

Name: The standard unbounded fan-in basis
Definition: \(\{\neg,(\land^n)_{n\in\mathbb N},(\lor^n)_{n\in\mathbb N}\}\).
Page: 10
Chapter: 1
Section: 2
Notation: \(B_1\)
Index: 12
Kind: Def

Definition: The class of all sets \(A\subseteq\{0,1\}^*\) for which there is a circuit family \(\mathbf C\) over basis \(B\) of size \(O(s)\) that accepts \(A\)
Page: 10
Chapter: 1
Section: 2
Variables: \(B\) a basis and \(s,d\in\mathbb N\to\mathbb N\).
Notation: \(\text{SIZE}_B(s)\)
Index: 13
Kind: Def

Q: [...] is an abbreviation for [...]
A: \(\text{FOO}\); \(\text{FOO}_{B_0}\)
Page: 11
Chapter: 1
Section: 2
Variables: \(s,d\in\mathbb N\to\mathbb N\)
\(\text{FOO}\) a family (Boolean/function) size/depth.
Index: 13
Kind: Def

Definition: \(\text{FOO}_{B_1}\)
Page: 10
Chapter: 1
Section: 2
Variables: \(s,d\in\mathbb N\to\mathbb N\) and \(\text{FOO}_B\) a class of family.
Notation: \(\text{UnbFOO}\)
Index: 13
Kind: Def

Q: [...] is defined as [...]
A: \(\text{FOO}(\mathcal F)\); \(\bigcup_{f\in\mathcal F}\text{FOO}(f)\)
Page: 11
Chapter: 1
Section: 2
Variables: \(\mathbf F\) a class of functions \(f:\mathbb N\to\mathbb N\)and \(\text{FOO}_B\) a class of family.
Index: 13
Kind: Def

Name: A length respecting function on binary words
Definition: A function \(f:\{0,1\}^*\to\{0,1\}^*\) such that whenever \(|x|=|y|\), then \(|f(x)|=|f(y)|\).
Page: 11
Chapter: 1
Section: 2
Index: 14
Kind: Def

Smaller0: ADD
Greater0: \(n^2\)
Page: 11
Chapter: 1
Section: 2
Index: 15
Kind: Theo
Smaller to greater: belongs to
Hide middle: yes
Prefix Greater: \(\text{FUnbSIZE-DEPTH}(\)
Greater1: \(1\)
Greater to smaller: contains
Connect Greater0: \(,\)
Suffix Greater: \()\)

Question: \(\text{SIZE-DEPTH}_{B\cup B_0}(s,d)=\)
Answer: \(\text{SIZE-DEPTH}(s,d)
Page: 12
Chapter: 1
Section: 2
Variables: \(B\) a bounded fan-in basis and \(s,d:\mathbb N\to\mathbb N\).
Index: 16
Kind: Prop

Question: \(\text{SIZE-DEPTH}_{B\cup B_1}(s,d)=\)
Answer: \(UnbSIZE-DEPTH(s,d)\)
Page: 12
Chapter: 1
Section: 2
Variables: \(B\) a bounded fan-in basis and \(s,d:\mathbb N\to\mathbb N\).
Index: 16
Kind: Prop

Definition: \(\text{SIZE-DEPTH}(s^2,d\log s)\)
Page: 12
Chapter: 1
Section: 2
Variables: \(s,d:\mathbb N\to\mathbb N\).
Notation: \(\text{UnbSIZE-DEPTH}(s,d)\)
Index: 17
Kind: Prop
Extra: =?

Smaller0: ADD
Greater0: \(n^4\)
Page: 12
Chapter: 1
Section: 2
Index: 18
Kind: Cor
Smaller to greater: belongs to
Hide middle: yes
Prefix Greater: \(\text{FSIZE-DEPTH}(\)
Greater1: \(\log n\)
Greater to smaller: contains
Connect Greater0: \(,\)
Suffix Greater: \()\)

Name: Polynomially length-bounded word function
Definition: \(f:\{0,1\}^*\to\{0,1\}^*\) such that there is a polynomial \(p\) such that for every \(x\in\{0,1\}^*\), \(|f(x)|\le p(|x|)\).
Page: 12
Chapter: 1
Section: 2
Index: 19
Kind: Def

Name: ITADD
Definition: Input: \(n\) numbers with \(n\) bits each,
Output: the sum of the input numbers in binary
Page: 13
Chapter: 1
Section: 2
Variables: \(n\in\mathbb N\)

Smaller0: Input: \(\log n\) numbers with \(n\) bits each,
Output: the sum of the input numbers in binary.
Greater0: \(n^4,\log n\)
Page: 14
Chapter: 1
Section: 2
Smaller to greater: belongs to
Hide middle: yes
Prefix Greater: \(\text{FSIZE-DEPTH}(\)
Name: LOGITADD
Greater to smaller: contains
Suffix Greater: \()\)
Suffix Smaller: It

Name: BCOUNT
Definition: Input: \(n\) bits,
Output: the number of 1
Page: 15
Chapter: 1
Section: 2
Index: 22
Kind: Cor
Extra: in binary ?

Smaller0: LOGITADD
Greater0: \(n^{O(1)} \)
Page: 15
Chapter: 1
Section: 2
Index: 21
Kind: Theo
Smaller to greater: belongs to
Hide middle: yes
Prefix Greater: \(\text{FUnbSIZE-DEPTH}(\)
Greater1: \(1\)
Greater to smaller: contains
Connect Greater0: \(,\)
Suffix Greater: \()\)

Name: MULT
Definition: Given two \(n\) bits number, comput their product.
Page: 016
Chapter: 1
Section: 3.2
Index: 23
Kind: Theo

Smaller0: «does the majority of the bits is 1 ?»
Greater0: \(\log(n)\)
Page: 016
Chapter: 1
Section: 3.3
Index: 24
Kind: Theo
Smaller to greater: belongs to
Hide middle: yes
Prefix Greater: \(\text{FDEPTH}(\)
Greater to smaller: contains
Prefix Smaller: MAJ is:
Suffix Greater: \()\)
Suffix Smaller: . It

Name: The inner product of \(\vec x\) and \(\vec y\)
Definition: \(\bigvee_{i=1}^nx_i\land y_i\).
Page: 17
Chapter: 1
Section: 3.4
Variables: \(\vec x=(x_1,\dots,x_n)\) and \(\vec y=(y_1,\dots,y_n)\) Boolean vectors.
Index: 25
Kind: Def

Smaller0: Inner product of boolean vectors
Greater0: \(n,1\)
Page: 17
Chapter: 1
Section: 3.4
Index: 26
Kind: Lem
Smaller to greater: belongs to
Hide middle: yes
Prefix Greater: \(\text{UnbSIZE-DEPTH}(\)
Greater to smaller: contains
Suffix Greater: \()\)

Name: The product of \(A\) and \(B\)
Definition: \(C=(c_{i,j})_{1\le i,j\le n}\) with \(c_{i,j}=(a_{i,1},\dots,a_{i,n})(b_{1,j},\dots,b_{n,j})\).
Page: 17
Chapter: 1
Section: 3.4
Variables: \(A=(a_{i,j})_{1\le i,j\le n}\), \(B=(b_{i,j})_{1\le i,j\le n}\) square Boolean matrices.
Index: 27
Kind: Def

Smaller0: Multiplication of boolean matrices
Greater0: \(n\)
Page: 17
Chapter: 1
Section: 3.4
Index: 28
Kind: Lem
Smaller to greater: belongs to
Hide middle: yes
Prefix Greater: \(\text{UnbSIZE-DEPTH}(\)
Greater1: \(1\)
Greater to smaller: contains
Connect Greater0: \(,\)
Suffix Greater: \()\)

Q: [...]
iff [...].
A: \(\bigvee_{i\ge0}A^i\) where \(A^0\) is the identity matrix and \(A^{i+1}=A^i A\); the matrix \(C\) such that \(c_{i,j}\) if there is a sequence \(i=k_0,\dots,k_n=j\) such that for all \(0\le m<n\), \(a_{k_m,k_{m+1} }\) is true. I.e. there is a path in the graph with \(n\) vertices, and edges from \(v\) to \(w\) if and only if \(a_{v,w}\) is true
Page: 17
Chapter: 1
Section: 3.4
Variables: \(A=(a_{i,j})_{1\le i,j\le n}\) a square Boolean matrices.
Index: 29
Kind: Def
Name: The transitive closure of \(A\)
Extra: Rem 30
Notation: \(A^*\)

Smaller0: The transitive closure of boolean matrices
Greater0: \(n^{O(1)},\log^2n\)
Page: 17
Chapter: 1
Section: 3.4
Index: 31
Kind: Theo
Smaller to greater: belongs to
Hide middle: yes
Prefix Greater: \(\text{FSIZE-DEPTH}(\)
Greater to smaller: contains
Suffix Greater: \()\)

Definition: The function associating to a word \(w\) of length \(n\) the \(i\)-th bit of the output of \(f(w)\)
Page: 18
Chapter: 1
Section: 4
Variables: \(r:\mathbb N\to\mathbb N\)
\(f:\{0,1\}^*\to\{0,1\}^*\) sending words of length \(n\) to words of length \(r(n)\).
\(n,i\in\mathbb N\)
Notation: \(f^n_i\)
Index: 32
Kind: Def

Definition: The set of functions \(f^n_i\).
Page: 18
Chapter: 1
Section: 4
Variables: \(r:\mathbb N\to\mathbb N\) and \(f:\{0,1\}^*\to\{0,1\}^*\) sending words of length \(n\) to words of length \(r(n)\).
Notation: bits(f)
Index: 32
Kind: Def

Page: 18
Definition: \(f\in\text{FSIZE-DEPTH}_{\mathcal B_1\cup\text{bits}(g)}(n^{O(1)},1)\).
Chapter: 1
Section: 4
Variables: \(f,g:\{0,1\}^*\to\{0,1\}^*\) be length-preserving
Notation: \(f\le_{\text{cd} }g\)
Name: \(f\) is constant-depth reducible to \(g\)
Kind: Def
Index: 33
Extra: Lem 36 1, 2
Order: partial

Page: 18
Definition: \(f\le_{\text{cd} }g\) and \(g\le_{\text{cd} }f\).
Chapter: 1
Section: 4
Variables: \(f,g:\{0,1\}^*\to\{0,1\}^*\) be length-preserving
Notation: \(f\cong_{\text{cd} }g\)
Kind: Def
Index: 33

Q: [...] and \([...]\in\text{FunBSIZE-DEPTH}(n^{O(1)},1)\) implies \([...]\in\text{FunBSIZE-DEPTH}(n^{O(1)},1)\)
A: \(f\le_{\text{cd} }g\); g; f
Page: 19
Chapter: 1
Section: 4
Variables: \(f,g:\{0,1\}^*\to\{0,1\}^*\) be length-preserving.
Index: 36 3
Kind: Lem

\(f\le_{\text{cd} }g\) and \(g\in\text{FSIZE-DEPTH}(n^{O(1)},\log n)\) implies \(f\in\text{FSIZE-DEPTH}(n^{O(1)},\log n)\)
Page: 19
Chapter: 1
Section: 4
Variables: \(f,g:\{0,1\}^*\to\{0,1\}^*\) be length-preserving
Index: 36 4
Kind: Lem

Smaller0: \(f\in\text{FUnbSIZE-DEPTH}(n^{O(1)},1)\)
Greater0: \(f\le_{\text{cd} }g\)
Page: 19
Chapter: 1
Section: 4
Variables: \(f,g:\{0,1\}^*\to\{0,1\}^*\) be length-preserving
Index: 36 5
Kind: Lem

Q: are constant-depth equivalent.
They belong to \(\text{FDEPTH}([...])\)
A: \log n
Page: 25
Chapter: 1
Section: 4.3
Index: 45, 46
Kind: Cor
ITADD, BCOUNT, UCOUNT, MAJ, MULT, ITMULT and SORT
Extra: Theo 40, Theo 37 and 38 useless because of this corollary

Name: ITMULT
Definition: input: \(n\) numbers in binary with \(n\) bits each.
Output: the product of the input numbers in binary
Page: 22
Chapter: 1
Section: 4.2

Name: SORT
Definition: input: \(n\) numbers in binary with \(n\) bits each.
Output: the \(n\) numbers in increasing order
Page: 24
Chapter: 1
Section: 4.3

Name: The \(k\)-bit representation of \(n\)
Definition: \(1^n0^{k-n}\)
Page: 24
Chapter: 1
Section: 4.3
Variables: \(n\le k\).
Notation: un\(_k(n)\)
Extra: unary

Definition: \(\{0,1\}^{\{ 0,1\}^n }\)
Page: 26
Chapter: 1
Section: 5.
Variables: \(n\le k\).
Notation: \(\mathbb B^n\)

Definition: \(\mathbb B^*\cup \mathbb B^1\cup\mathbb B^2\).
Page: 26
Chapter: 1
Section: 5.
Notation: \(\widehat{ \mathcal B}\)

Q: [...] [...].
A: The ratio of all \(n\)-ary Boolean functions that can be computed by circuits over \(\circ B\) with \((1-\epsilon)\frac{2^n}n\) gates; approaches 0 as \(n\to\infty\)
Page: 26
Chapter: 1
Section: 5.
Variables: \(\epsilon>0\)
Index: 47
Kind: Theo
Name: Shannon Theorem

Question: Every \(n\)-ary boolean function can be computed by circuits with
Answer: \(\frac{2^n}n+o\left(\frac {2^n}n\right)\) gates over the basis \(\{0,1,\oplus,\land\}\).
Page: 31
Chapter: 1
Section: 5.2
Variables: \(n\in \mathbb N\).
Index: 51
Kind: Theo
Name: Lupanov

Smaller0: \(f\) is computed by an oblivious TM in time \(g\)
Greater0: \(g\)
Page: 26
Chapter: 2
Section: 1
Variables: \(g:\mathbb N\to\mathbb N\)
\(f:\{0,1\}^*\to\{0,1\}^*\) length preserving
Index: 5
Kind: Lem
Prefix Greater: \(f\in\text{FSIZE}(\)
Suffix Greater: \()\)

Smaller0: \(f\in\text{FDTIME}(t)\)
Greater0: \(O(t\log t)\)
Page: 27
Chapter: 2
Section: 1
Variables: \(t:\mathbb N\to\mathbb N\) greater than the identity function, \(f:\{0,1\}^*\to\{0,1\}^*\) length preserving.
Index: 6
Kind: Lem
Prefix Greater: \(f\) is computed by an oblivious TM in time

Smaller0: \(f\) is computed by a TM in time \(t\)
Greater0: \(t\log t\)
Page: 27
Chapter: 2
Section: 1
Variables: \(t:\mathbb N\to\mathbb N\) greater than the identity function, \(f:\{0,1\}^*\to\{0,1\}^*\) length preserving.
Index: 7
Kind: Theo
Hide middle: yes
Prefix Greater: \(f\in\text{FSIZE}(\)
Suffix Greater: \()\)

Q: \(\text{NSPACE}(s)\subseteq\text{DEPTH}([...])\)
A: s^2
Page: 41
Chapter: 2
Variables: \(t:\mathbb N\to\mathbb N\) greater logarithm.
Index: 9
Kind: Theo

Name: The advice class
Definition: The set of languages \(A\subseteq\{0,1\}^*\) for which there exists \(B\in\mathcal K\) and \(f\in\mathcal F\) such that for all \(x\), \(x\in A\) iff \(\langle x,f(1^{|x|})\rangle\in B\).
Page: 42
Chapter: 2
Section: 3
Variables: \(\mathcal K\subseteq\mathcal P(\{0,1\}^*)\),
\(\mathcal F\) a class of function \(\{0,1\}^*\to\{0,1\}^*\).
Notation: \(\mathcal K/\mathcal F\)
Index: 11
Kind: Def

Definition: The set of functions \(h:\{0,1\}^*\to\{0,1\}^*\) such that \(|h(x)|\le f(|x|)\) for all words \(x\).
Page: 43
Chapter: 2
Section: 3
Variables: \(f:\mathbb N\to\mathbb N\)
Notation: \(\mathbf F(f)\)
Index: 12
Kind: Def

Definition: \(\bigcup_{f\in\mathcal F}\mathbf F(f)\).
Page: 43
Chapter: 2
Section: 3
Variables: \(\mathcal F\subseteq \mathcal P(\mathbb N\to\mathbb N)\).
Notation: \(\mathbf F(\mathcal F)\)
Index: 12
Kind: Def

Name: An admissible encoding scheme of \(\mathcal C\)
Definition: An ordering of the elements of \(B\), a polynomial \(p\), a numbering of the gates of \(C_n\), with input first, output last, such that the numbers are at most \(p(s(n))\).
The encoding of a gate is its number, the number of its label, and the numbers of its predecessors. The encoding of the circuit is the sequence of encoding of the gates.
Page: 43
Chapter: 2
Section: 3
Variables: \(\mathcal C=(C_n)\) a circuit family with basis \(B\).
Notation: \(\overline {C_n}\)
Index: 14
Kind: Def

Smaller0: BCOUNTS
Greater0: \(\log(n)\)
Page: 15
Chapter: 1
Section: 2
Index: 22
Kind: Cor
Smaller to greater: belongs to
Hide middle: yes
Prefix Greater: \(\text{FDEPTH}(\)
Greater to smaller: contains
Suffix Greater: \()\)

Smaller0: \(\text{SIZE}(f)\)
Greater0: \(\text{DTIME}(s^2)/\mathbf F(O(s\log s))\)
Page: 44
Chapter: 2
Section: 3
Variables: \(f:\mathbb N\to\mathbb N\)
Index: 15
Kind: Theo
Smaller to greater: \(\subseteq\)
Assuming: \(f(n)\ge n\)
Greater to smaller: \(\supseteq\)

\(f(n)\ge n\) implies \(\text{SIZE}(f^{O(1)})= \text{DTIME}(f^{O(1)})/\mathbf F(t^{O(1)})\)
Page: 44
Chapter: 2
Section: 3
Variables: \(f:\mathbb N\to\mathbb N\)
Index: 16
Kind: Cor

Smaller0: \(\text{SIZE}(n^{O(1)})\)
Greater0: \(\mathbf P/\text{Poly} \)
Page: 44
Chapter: 2
Section: 3
Index: 17
Kind: Cor
Smaller to greater: =

\(d(n)\ge \log n\) implies \(\text{DEPTH}(d)\subseteq \text{DSPACE}(d)/\mathbf F\left(2^{O(d)}\right) \).
Page: 45
Chapter: 2
Section: 3
Variables: \(f:\mathbb N\to\mathbb N\)
Index: 18
Kind: Theo

Smaller0: \(\text{DEPTH}\left(\log\right)\)
Greater0: \(\text{L}/\text{Poly} \)
Page: 46
Chapter: 2
Section: 3
Index: 20
Kind: Cor
Smaller to greater: \(\subseteq\)
Greater to smaller: \(\supseteq\)

Name: \(L\) (respectively \(P\))-uniform circuit family
Definition: A circuit family such that there is an admissible encoding scheme such that the map \(1^n\mapsto\overline{C_n}\) is in FDSPACE\((\log n)\) (respectively FDTIME\((n^{O(1)})\)).
Page: 47
Chapter: 2
Section: 3
Variables: \(\mathcal C=(C_n)\) a circuit family.
Index: 22
Kind: Def

Name: U_L-CLASS, (respectively U_P-CLASS)
Definition: The subset of this class which is L (respectively P)-uniform
Page: 47
Chapter: 2
Section: 3
Variables: CLASS a class of circuit
Index: 22
Kind: Def

\(f(n)\ge n\) and \(1^n\mapsto f(n)\) is computable in space \(O(\log (f(n)))\) implies \(\text{DTIME}(f)\subseteq\text{U}_L-\text{SIZE}(f\log f)\).
Page: 51
Chapter: 2
Section: 4
Variables: \(f:\mathbb N\to\mathbb N\)
Index: 27
Kind: Theo

Smaller0: \(\text{U}_L-\text{SIZE}(f)\)
Greater0: \(\text{DTIME}(f^{O(1)})\)
Page: 52
Chapter: 2
Section: 4
Variables: \(f:\mathbb N\to\mathbb N\)
Index: 28
Kind: Theo
Smaller to greater: \(\subseteq\)
Assuming: \(f\ge n\)
Greater to smaller: \(\supseteq\)

\(f\ge n\) and \(1^n\mapsto t(n)\) is computable in space \(O(\log (f(n)))\) implies \(\text{U}_L-\text{SIZE}(f^{O(1)})=\text{DTIME}(t^{O(1)})\).
Page: 52
Chapter: 2
Section: 4
Variables: \(f:\mathbb N\to\mathbb N\)
Index: 29
Kind: Cor

Smaller0: \(\text{U}_L-\text{SIZE}(n^{O(1)})\)
Greater0: \(P\)
Page: 52
Chapter: 2
Section: 4
Index: 30
Kind: Cor
Smaller to greater: =

\(f\ge \log\) is space constructible implies \(\text{U}_L-\text{DEPTH}(f)=\text{DSPACE}\left(f\right)\).
Page: 52
Chapter: 2
Section: 4
Variables: \(f:\mathbb N\to\mathbb N\)
Index: 32
Kind: Theo

Name: Direct connection language of \(\mathcal C\)
Definition: \(g\) a number of gate \(v\in C_{|y|}\),
Page: 49
Chapter: 2
Section: 4
Variables: \(B\) a basis
\(\mathcal C=(C_n)\) a circuit family.
Index: 24
Kind: Def
Definition2: \(p\in\{0,1\}^*\),
Conjdef: The set of \(\langle y,g,p,b\rangle\) with
Definition3: If \(p=\epsilon\), then \(b\) is the index of the function of \(B\) computed at the node \(v\)
Abbreviation: \(L_{\text{DC}}(\mathcal C)\)
Definition4: If \(p=\text{bin}(k)\), then \(b\) is the number of the \(k\)-th predecessor gate to \(v\)

Name: The size of \(\mathbf C\)
Definition: The function associating \(i\in\mathbb N\) to the size of \(C_i\).
Page: 10
Chapter: 1
Section: 2
Variables: \(B\) a basis,
\(\mathbf C=(C_0,C_1,\dots)\) a circuit family over \(B\) computing a function \(f\)
Index: 11
Kind: Def

Definition: The class of all sets \(A\subseteq\{0,1\}^*\) for which there is a circuit family \(\mathbf C\) over basis \(B\) of depth \(O(d)\) that accepts \(A\)
Page: 10
Chapter: 1
Section: 2
Variables: \(B\) a basis and \(s,d\in\mathbb N\to\mathbb N\).
Notation: \(\text{DEPTH}_B(d)\)
Index: 13
Kind: Def

Definition: The class of all sets \(A\subseteq\{0,1\}^*\) for which there is a circuit family \(\mathbf C\) over basis \(B\) of size \(O(s)\) and depth \(O(d)\) that accepts \(A\)
Page: 10
Chapter: 1
Section: 2
Variables: \(B\) a basis
\(s,d\in\mathbb N\to\mathbb N\).
Notation: \(\text{SIZE-DEPTH}_B(s,d)\)
Index: 13
Kind: Def

Definition: the class of all functions \(f:\{0,1\}^*\to\{0,1\}^*\) for which there is a circuit family \(\mathbf C\) over basis \(B\) of size \(O(s)\) that computes \(f\)
Page: 10
Chapter: 1
Section: 2
Variables: \(B\) a basis and \(s,d\in\mathbb N\to\mathbb N\).
Notation: \(\text{FSIZE}_B(s)\)
Index: 13
Kind: Def

Definition: the class of all functions \(f:\{0,1\}^*\to\{0,1\}^*\) for which there is a circuit family \(\mathbf C\) over basis \(B\) of depth \(O(d)\) that computes \(f\)
Page: 10
Chapter: 1
Section: 2
Variables: \(B\) a basis and \(s,d\in\mathbb N\to\mathbb N\).
Notation: \(\text{FDEPTH}_B(d)\)
Index: 13
Kind: Def

Definition: the class of all functions \(f:\{0,1\}^*\to\{0,1\}^*\) for which there is a circuit family \(\mathbf C\) over basis \(B\) of size \(O(s)\) and depth \(O(d)\) that computes \(f\)
Page: 10
Chapter: 1
Section: 2
Variables: \(B\) a basis and \(s,d\in\mathbb N\to\mathbb N\).
Notation: \(\text{FSIZE-DEPTH}_B(s,d)\)
Index: 13
Kind: Def

Smaller0: \(\text{NSPACE}\left(f\right)\)
Greater0: \(\text{U}_L-\text{DEPTH}(f)\)
Page: 52
Chapter: 2
Section: 4
Variables: \(f:\mathbb N\to\mathbb N\)
Index: 31
Kind: Theo
Smaller to greater: \(\subseteq\)
Assuming: \(f\ge \log\) is space constructible
Greater to smaller: \(\supseteq\)

Smaller0: \(\text{DEPTH}\left(\log^{O(1)}\right)\)
Greater0: \(\text{DSPACE}(\log^{O(1)})/\mathbf F\left(2^{\log^{O(1)} }\right)\)
Page: 46
Chapter: 2
Section: 3
Variables: \(f:\mathbb N\to\mathbb N\)
Index: 19
Kind: Cor
Smaller to greater: =

Name: UCOUNT
Definition: Input: \(n\) bits.
Output: the \(n\)-bit unary representation of the number of 1's of those bits.
Page: 24
Chapter: 1
Section: 4.3