Title: Theory / Unimportant / CS / Fundamental / Complexity / Complexity Arora Barak/{ / Interactive proofs
Tags: fromMath mathToDef examplesSwitchExample1 mathToSee

Definition: The class of languages, accepted by a probabilistict polynomial-time TM \(V\) that can have a \(k\)-round interaction with a function \(P:\{0,1\}^*\to\{0,1\}\) which outputs the correct answer with probability at least 2/3 or \(1-2^{-n^s}\).
Page: 146
Chapter: 8
Section: 1
Variables: \(k\ge 1\)
Notation: IP[k]

Smaller0: \(\mathbf{IP}\)
Greater0: \(PSPACE\)
Page: 147
Chapter: 8
Section: 1
Index: 2
Smaller to greater: \(\subseteq\)
Greater to smaller: \(\supseteq\)

Name: A \(k\)-round interaction
Definition: The sequence of strings \(a_1,\dots,a_k\in\{0,1\}^*\) such that \(a_i=f_{i\mod 2}(x,r_{i\mod 2}a_1,\dots,a_{i-1})\), with \(r_0,r_1\) two random strings.
Page: 144
Chapter: 8
Section: 1
Variables: \(k\ge 1\), \(f_0,f_1:\{0,1\}^*\to\{0,1\}^*\)
Notation: \(\langle f_0,f_1\rangle(x)\)
Index: 2
Kind: Def

Page: 148
Chapter: 8
Section: 1.3
Name: Languages in IP
Q: -[...]
-[...].
A: Graph nonisomorphism; \((a,p)\) such that \(a\) is not a square modulo \(p\)

Name: Arthur-Merlin protocol
Definition: The restriction of \(\mathbf{IP}[k]\) where the verifier only sends the random bits.
Page: 150
Chapter: 8
Section: 2
Variables: \(k\ge 1\)
Context: Complexity theory
Notation: \(AM[k]\) protocol
Name2: public coin

Definition: \(AM[2]\)
Page: 150
Chapter: 8
Section: 2
Notation: AM

Name: Merlin-Arthur
Definition: Prover sends a message, verifier toss coins and computes in P-time its decision.
Page: 150
Chapter: 8
Section: 2
Abbreviation: MA

Question: \(AM=\)
Answer: \(BP\cdot NP\)
Page: 151
Chapter: 8
Section: 2

Question: \(AM[k]=\)
Answer: \(AM\)
Page: 151
Chapter: 8
Section: 2
Variables: \(k\ge2\)
Index: 3

Smaller0: \[\mathbf{IP}[k]\]
Greater0: \[\mathbf{AM}[k+2]\]
Page: 151
Chapter: 8
Section: 2.1
Variables: \(k:\mathbb N\to\mathbb N\)
Index: 2
Kind: Theo
Smaller to greater: \(\subseteq\)
Greater to smaller: \(\supseteq\)

Name: Problem expressible in \(\mathbf{AM}[2]\)
Page: 151
Chapter: 8
Section: 2.1
Index: 3
Kind: Theo
Example: GNI

Name: Set lower bound protocol
Definition: Given a set \(S\) known to both prover and verifier. Assuming membership in \(S\) can be easily certified. A public-coin protocal which allow the prover to certify the cardinality of \(S\).
Page: 152
Chapter: 8
Section: 2.2

Name: A set of pairwise independant functions
Definition: A set \(\mathcal H_{n,k}\) such that, for every \(x,x'\in\{0,1\}^n\) distinct, for every \(y,y'\in\{0,1\}^k\), \(Pr_{h\in R\mathcal H_{n,k} }[h(x)=y\land h(x')=y']=2^{-2k}\).
Page: 152
Chapter: 8
Section: 2.2
Variables: \(n,k\in\mathbb N\)
Index: 14, 2
Kind: Def, Theo
Example: The set of function \(h_{a,b}:x\mapsto ax+b\), where \(x,a,b\in\text{GF}(2^n)\)
Typ: A set of functions from \(\{0,1\}^n\to\{0,1\}^k\).
Denoted by: \(\mathcal H_{n,k}\)

Smaller0: NP-complete
Greater0: \(\Sigma_2=\Pi_2\)
Page: 156
Chapter: 8
Section: 2.4
Index: 18
Kind: Theo
Hide middle: yes
Prefix Smaller: GI is

Smaller0: IP
Greater0: PSPACE
Page: 158
Chapter: 8
Section: 2.4
Index: 19
Kind: Theo
Smaller to greater: equals
Extra: Et ATIME ?

Definition: \(\{\langle \phi,K\rangle\mid \phi\text{ is a 3-CNF formula and it has exactly $K$ satisfying assignments}\}\)
Page: 158
Chapter: 8
Section: 2.4
Notation: \(\# SAT_D\)
Index: 20
Kind: Def