Title: Theory / Unimportant / CS / Fundamental / Complexity / Wigderson / 7 Randomness
Tags: effectNew fromAlgorithm hasNotNewEffectReturnsMeaning instructionToImplementation hasSeenConjDef

Name: The \(n\times n\) Vandermonde matrix
Definition: The matrix whose entry \((i,j)\) is \(x_i^{j-1}\)
Page: 84
Chapter: 7
Section: 1
Variables: \(n\in\mathbb N\)
Abbreviation: \(V(x_1,\dots,x_n)\)

Question: \(\mathrm{det}V(x_1,\dots,x_n)\)
Answer: \(\equiv\prod_{i<j}(x_i-x_j)\)
Page: 84
Chapter: 7
Section: 1
Variables: \(n\in\mathbb N\)
Kind: Prop

Smaller0: \(x_1,\dots,x_3\) are randomly selected from \(\{1,\dots,3\mathrm{deg }q\}\)
Greater0: \(\mathrm{Pr}[q(r_1,\dots,r_n)=0]\le \frac13\)
Page: 84
Chapter: 7
Section: 1
Variables: \(n\in\mathbb N\)
\(q\) a polynomial in \(n\) variables
Index: 2
Kind: Prop

Page: 84
Implementation: Take \(n\) values \(\{x_1,\dots,x_n\}\) randomly in \(\{1,\dots,3d\}\), returns true if \(q(x_1,\dots,x_n)\ne 0\)
Section: 1
Chapter: 7
Effect: Whether \(q\ne 0\) with probability at least 2/3
Variables: \(n\mathbb N\)
\(q\) a polynomial in \(n\) variables
Context: Polynomial
Index: 2
Kind: Prop

Name: Bounded error, Probabilisty, Polynomial time
Definition: there is a probabilistic polynomial time algorithm \(A\) such that \(\mathrm{Pr}[A(x)\ne f(x)]\le 1/3\)
Page: 85
Chapter: 7
Section: 1
Index: 3
Kind: Def
Definition2: there is a deterministic polynomial time algorithm \(A'\) such that \(A'(x,r)= f(x)\) for at least two third of the \(r\in\{0,1\}^{p(|x|)}\), for some polynomial \(p\)
Conjdef: A function \(f:\mathbf{I\to I}\) such that, equivalently
Abbreviation: \(\mathcal{BPP}\)

Name: A probabilistic algorithm
Definition: An algorithm with access to a fair coin to read randomly one of two values.
Page: 85
Chapter: 7
Section: 1
Index: 3
Kind: Def

Smaller0: \(\mathcal BPP\)
Greater0: \(\mathcal P/\mathrm{poly}\)
Page: 86
Chapter: 7
Section: 1
Index: 4
Kind: Theo
Smaller to greater: \(\subseteq\)
Greater to smaller: \(\supseteq\)
Hide sides: yes

Name: Problem efficiently solved probabilisticly, but not deterministically
Page: 86
Chapter: 7
Section: 1
Example: Generating prime in the interval \([x,2x]\)
Example2: Polynomial factoring
Example3: Permanent approximation
Example4: Volume approximation

Page: 86
Implementation: Choose randomly a number in \([x,2x]\). Test its primality. Repeat until a prime is found.
Section: 1
Chapter: 7
Effect: Generating with high probability a prime in the interval \([x,2x]\)
Variables: \(x\in\mathbb N\)
Time complexity: polynomial