Title: Theory / Unimportant / CS / Fundamental / Complexity / Complexity Arora Barak/{ / Communication complexity
Tags: fromMath mathToDef hasSeenConjDef mathToSee

Name: A \(t\)-round two-party protocol
Definition: A sequence of \(t\) functions \(P_1,\dots,P_t:\{0,1\}^*\to\{0,1\}^*\).
Page: 271
Chapter: 13
Section: 1
Variables: \(f:\{0,1\}^{2n}\to\{0,1\}\), \(t\in\mathbb N\)

Name: The execution of \(\Pi\) on \(x_0,x_1\)
Definition: A sequence \(p_{k}=P_{k}\left(p_1,\dots,p_{k-1},x_{k\mod 2}\right)\)
Page: 271
Chapter: 13
Section: 1
Variables: \(t\in\mathbb N\)
\(P_1,\dots,P_t:\{0,1\}^*\to\{0,1\}^*\) a \(t\)-round two-party protocol \(\Pi\)
\(x_0,x_1\in\{0,1\}^n\)
Kind: Def

Q: \(\Pi\) is [...] if [...].
A: valid for \(f\); for every \(x_0,x_1\in\{0,1\}^n\), the last element of its execution is \(f(x_0,x_1)\)
Page: 271
Chapter: 13
Section: 1
Variables: \(f:\{0,1\}^{2n}\to\{0,1\}\),
\(t\in\mathbb N\)
\(P_1,\dots,P_1:\{0,1\}^*\to\{0,1\}^*\) a \(t\)-round two-party protocol \(\Pi\).
Kind: Def

Name: Communication complexity of \(\Pi\)
Definition: The maximal (for the \(x_0,x_1\)) sum of the length of the \(p_i\).
Page: 271
Chapter: 13
Section: 1
Variables: \(f:\{0,1\}^{2n}\to\{0,1\}\)
\(t\in\mathbb N\)
\(P_1,\dots,P_1:\{0,1\}^*\to\{0,1\}^*\) a \(t\)-round two-party protocol \(\Pi\)
Kind: Def

Name: Communication complexity of \(f\)
Definition: The minimal (considering all \(t\)-round protocol \(\Pi\)) communication complexity of \(\Pi\).
Page: 271
Chapter: 13
Section: 1
Variables: \(f:\{0,1\}^{2n}\to\{0,1\}\),
\(t\in\mathbb N\).
Kind: Def

Question: The communication complexity of parity is
Answer: 2.
Page: 271
Chapter: 13
Section: 1
Index: 2
Kind: Ex

Question: The problem: given \((x,y)\) accepts if \(y=1^n\) and \(x\) encodes a TM which accepts \(y\).
The communication complexity of this problem is
Answer: 2.
Page: 271
Chapter: 13
Section: 1
Index: 2
Kind: Ex

Question: The communication complexity of Equality is
Answer: at least \(n\).
Page: 272
Chapter: 13
Section: 2
Variables: \(n\in\mathbb N\).
Index: 4
Kind: Theo

Question: The communication complexity of Disjoint is
Answer: at least \(n\).
Page: 273
Chapter: 13
Section: 2
Variables: \(n\in\mathbb N\).
Index: 6
Kind: Ex

Name: A fooling set
Definition: \(f\) is constant on \(S\)
Page: 272
Chapter: 13
Section: 2
Variables: \(n\in\mathbb N\), \(f:\{0,1\}^{2n}\to\{0,1\}\)
Index: 5
Kind: Lem
Definition2: for every \(\langle x,y\rangle,\langle x',y'\rangle\in S\) either \(f(\langle x,y'\rangle)\) or \(f(\langle x',y\rangle)\) is distinct from \(f(\langle x,y\rangle)\).
Conjdef: A set \(S\subseteq\{0,1\}^{2n}\) such that

Smaller0: \(f\) has a size \(M\) fooling set
Greater0: the communication complexity of \(f\) is at least \(\log M\)
Page: 272
Chapter: 13
Section: 2
Variables: \(n,M\in\mathbb N\),
\(f:\{0,1\}^{2n}\to\{0,1\}\)
Index: 5
Kind: Lem
Hide middle: yes