Communication Complexity

• $D_2(F)$ = min cost of a protocol computing F. (min of max)
• $R_2^e(F)$ min cost of a randomized protocol computing $F$.
• $0 \lte R \lte D \lte n+1$
• If TM decides L in $T(n)$ time and $S(n)$ space on input $3n$, then $T(n)*S(n)=\Omega(n^2)$
• $C^D(F)$ be the minimum number of monochromatic rectangles to partition
• $2^c \ge C^D(F)$

Markov Chain

The future is independent of the past, given the present

• stationary/invariant distribution
• Mean Recurrence Theorem
• transition matrix: $K[i, j] = Pr[X_1=j | X_0 = i]$
• Probability of being at state $i$ after $t$ steps: $\pi_t[i] = (\pi_0K^t)[i]$
• $E[T_{ii}] = E[#\text{steps to go from i to i}]$ = $1/\pi[i]$

Midterm 3 Review

Polynomial And Field

• There is a field with q elements iff q is a power of prime
• isomorphism: all fields with q elements have the same add&mult table, just renaming
• F[x] denotes the set of polynomials with variable x and coeffs. in field F. F[x] is not a field because division is not well-defined
• Polynomial division: deg(R(x)) < deg(B(x))
• A nonzero degree-d polynomial has at most d roots(depending on which field it may vary)
• There is exactly one poly of degree <= d which satisfies d+1 data points.
• Reed-Solomon Code: Sending as polynomials to avoid loss. 1. k erasures: send d+k+1 value-pairs 2. k corruptions: send d+2k+1 pairs, then there is a unique poly that differs with data at at most k points.

  Cryptography

• Euler’s Theorem & Fermat’s Little Theorem
• One-time pad (XOR); cannot be reused; Shannon’s Theorem: cannot have a pad smaller than the key size
• Diffie-Hellman Key Exchange: prime p, generator b, random r1 -p, b, $b^{r1}$> random r2 -> $b^{r2}$

• Public Secure Key: RSA

• Monte Carlo: possible to make errors, guarantee runtime

  • Min-cut: poly time. 1 - $\frac{1}{e}$
• Las Vegas : guarantee answer, possible worst running time
  • Quicksort

Primality testing

• Miller-Rabin: $O(n^2)$, with error rate $2^{-100}$
• To compute $A^B mod c$, repeatedly square $A$ and mod $c$. $O(n^2\log(n))$
• Reciprocal
• Euler totient: $\phi(x)$
• Euler’s theorem: $A^{\phi(M)} \equiv_M 1$, A,M relatively prime
• Fermat’s little theorem: $A^{p-1}\equiv_p 1$

Probability

• RandInt(m): 1, 2, 3, … m with $p=\frac{1}{m}$
• Bernoulli(p): 1 with $p=p$

outcome: A leaf in probability tree

Sample Space: Set of all outcomes

Event: A subset of outcomes

Law of Total Probability: $p[b] = p[a] p[b|a] + p[a^c] p[b|a^c]$

Independence of Multiple Events: for all subsets, for all size.

Random Variable: function from sample space to reals.

Indicator: R.V. x which is 1 when event A occurs, 0 otherwise.