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

Partial SAT Algorithms

1. run very fast
2. always give the right answer
3. may time out (i.e., will give up on certain instances)

“Key question: can you make my algorithm fail?”

our answer…

• uniform random 3cnf instances
• n: number of variables
• \(\triangle\), “clause density”: the number of clauses; where \(\Delta = \frac{n}{m}\).
• output \(\phi\), \(\Delta\) n random clauses, independently chosen

SAT or UNSAT

Sampling \(\phi \sim R_{3}\qty(n, \triangle)\) likely to be SAT or UNSAT? By your choice of \(\Delta\), as: \(\Delta \geq 5.2 = \qty(\log_{\frac{7}{8}} \qty(\frac{1}{2}))\), then as \(\lim_{n\to \infty } \text{Pr}_{\phi \sim R_{3}\qty(n, \Delta)}\qty [\phi \text{SAT}] =0\).

Formal Formulation of Optimization

If we want to write down an optimization problem…

\begin{align} \min_{x} f(x) \\ s.t: x \in \mathcal{X} \end{align}

where:

• \(x\): “design point” (usually a vector representing the thing you are trying to optimize)
  • which is an assignment of “design variable” to values (width, height, etc.)
• \(\mathcal{X}\): a feasible set of design points that satisfy the constraint
• \(f: \mathcal{X} \to \mathbb{R}\): the objective function, which
• \(x^{*}\): the minimizer—one (or many) points that satisfy the minimization scheme

Conventionally, we minimize.