Title: Theory / Unimportant / CS / Fundamental / Complexity / Complexity Arora Barak/{ / Decision tree
Tags: fromMath mathToDef interval mathToSee

Name: A decision tree
Definition: A tree for which each internal node is labeled with some \(x_i\), and two outgoing edges labeled \(0\) and \(1\). Each leaf is labelled 0 or 1.
Page: 259
Chapter: 12
Section: 1

Q: [...] is [...].
A: A decision tree for \(f(x)\); a decision tree such that, for each \(w\in\{0,1\}\), \(f(w)\) is the value obtained when, at each node labelled by \(x_i\), the \(w_i\)-th node is taken
Page: 259
Chapter: 12
Section: 1
Variables: \(f:\{0,1\}^n\to \{0,1\}\)

Name: Decision tree complexity of \(f\)
Definition: \[\text{min}_{t\in\mathcal T_f}\text{max}_{x\in\{0,1\}^n}cost(t,x)\].
Page: 260
Chapter: 12
Section: 1
Variables: \(f:\{0,1\}^n\to \{0,1\}\)
Notation: \(D(f)\)
Kind: Def

Definition: The set of decision tree for \(f\).
Page: 260
Chapter: 12
Section: 1
Variables: \(f:\{0,1\}^n\to \{0,1\}\)
Context: Complexity
Notation: \(\mathcal T_f\)
Kind: Def

Name: The cost of \(t\) on \(x\)
Definition: The number of bits of \(x\) examined by \(t\).
Page: 260
Chapter: 12
Section: 1
Variables: \(f:\{0,1\}^n\to \{0,1\}\),
\(t\in\mathcal T_f\)
\(x\in\{0,1\}^n\)
Context: decision tree
Kind: Def

Question: The decision tree complexity of OR is
Answer: \(n\).
Page: 260
Chapter: 12
Section: 1
Index: 2
Kind: Ex

Smaller0: \(C(f)\)
Greater0: \(D(f)\)
Page: 260,262, 263
Chapter: 12
Section: 1
Variables: \(f:\{0,1\}^n\to\{0,1\}\)
Index: ,,5
Kind: ,,Theo
Smaller to greater: \(\le\)
Greatest: \(\min\left(n,C(f)^2\right)\)

Question: The decision tree complexity of graph connectivity, with \(n\) nodes, is
Answer: \({n\choose 2}\).
Page: 260
Chapter: 12
Section: 1

Name: AND-OR function
Definition: The function \(\{0,1\}^{2^k}\mapsto\{0,1\}\), such that:
-\(f_{1}(x_1)=x_1\),
-\(f_{k}(x_1,\dots,x_{2^k})=f_{k-1}(x_1,\dots,x_{2^{k-1} })\#_kf_{k-1}(x_{2^{k-1}+1},\dots,x_{2^{k} })\), with \(k>0\), \( \#_0\) being \(\lor\) and \(\#_{1}\) being \(\land\).
Page: 261
Chapter: 12
Section: 1
Variables: \(k\in\mathbb N\).

Question: The decision tree complexity of AND-OR is
Answer: \(2^k\).
Page: 261
Chapter: 12
Section: 1
Variables: \(k\in\mathbb N\)

Name: Adress function problem
Definition: Given \(x_1,\dots,x_k,y_1,\dots,y_{2^k}\), return \(y_{x_1\dots x_k}\).
Page: 261
Chapter: 12
Section: 1
Variables: \(k\in\mathbb N\)

Question: The decision tree complexity of Adress function problem is
Answer: at most \(k+1\).
Page: 262
Chapter: 12
Section: 1
Variables: \(k\in\mathbb N\)

Name: A \(b\)-certificate for \(x\)
Definition: A subset \(S\subseteq\{0,1\}^n\) such that \(f(x')=b\) for every \(x'\) such that \(x'_{|S}=x_{|S}\).
Page: 262
Chapter: 12
Section: 2
Variables: \(f:\{0,1\}^n\to \{0,1\}\)
\(x\in\{0,1\}^n\)
\(b\in\{0,1\}\)
Context: Decision tree
Index: 3
Kind: Def

Name: Certificate complexity of \(f\)
Definition: The minimum \(k\) such that every string \(x\) has a \(f(x)\)-certificate of size at most \(k\).
Page: 262
Chapter: 12
Section: 2
Variables: \(f:\{0,1\}^n\to \{0,1\}\),
Context: Computational complexity
Notation: \(C(f)\)
Index: 3
Kind: Def

Question: The size of 1-certificate of graph connectivity, with \(m\) vertex, is
Answer: \(m-1\).
Page: 262
Chapter: 12
Section: 2
Index: 4
Kind: Ex

Question: The size of 0-certificates of graph connectivity, with \(m\) vertex, is
Answer: \(m^2/4\).
Page: 262
Chapter: 12
Section: 2
Index: 4
Kind: Ex

Question: The certificate complexity of graph connectivity, with \(m\) vertex, is
Answer: \(m^2/4\).
Page: 262
Chapter: 12
Section: 2
Index: 4
Kind: Ex

Question: The certificate complexity of AND-OR, is
Answer: at most \(2^{\lceil k/2\rceil}\).
Page: 262
Chapter: 12
Section: 2
Variables: \(k\in\mathbb N\)
Index: 4
Kind: Ex