stretching randomness

Goal: take \(S \sim \qty {\pm 1}^{l}\), we want to stretch this randomness \(\qty {\pm 1}^{n}\) where \(n = 2^{\theta\qty(l)}, l = \theta \qty(\log n)\).

Two main parts:

1. combinatorial designs
2. Yao’s Next-Bit Prediction Lemma

We can choose sufficiently small \(l\), in particular to be \(l = c \log n\), because then we can iterate over all seeds in time \(2^{l} = n^{c}\).

A Tour Through 254B’s Complexity Theory

Chapter 1: No School like the Old School

6 lectures, 4 theorems from the 70s.

the *relavitization barrier" to P vs. NP

• what has diagonalization proved?

  It shows a lot of impossibilities (“x can’t be applied to y”)

  • Cantor’s theorem
  • Godel’s incompleteness
  • halting problem
  • time/space hierarchy theorems

Hopcroft-Paul-Valiant

“On space versus time”

which ultimately shows P = BPP.

hardcore lemma

Goal: can we find a single set of \(x \in \qty {\pm 1}^{h} = H\) where \(|H| \geq \frac{\delta}{2}\), such that for \(f : \qty {\pm 1 }^{h} \to \qty {\pm 1}\), for all circuits of size \(S\), commuting \(f\) on inputs in \(H\) is hopelessly hard (i.e., the \(\mathbb{Pr}_{x \in H} \qty [f\qty(x) =c\qty(x)] \leq \frac{1}{2} + \frac{\varepsilon}{2} \implies \mathbb{E}_{x \sim H} \qty [f\qty(x) c\qty(x)] \leq \varepsilon\).

Part 1

• Relativization Barrier to P vs. NP: \(\exists\) oracles \(A\) such that \(P^{A} = NP^{A}\),
• Space and Time: \(\text{TIME}\qty(t) \subseteq \text{SPACE}\qty(\frac{t\qty(n)}{\log \qty(t\qty(n))} )\)
  • pebbling game (constant degree digraph, can only place if pebble adjacent): can be pebbled with \(\leq O\qty( \frac{v}{\log v})\) pebbles
• Time Space Constraints:
  • \(\text{SAT} \not \in \text{TISP}\qty(n^{1.8}, n^{o\qty(1)})\), no one machine can do both
• Ladner’s Theorem: assuming P != NP, there are NP-intermediate languages

Part 2

Hardness vs. Randomness