Houjun Liu

SU-CS254 MAR032025

Today: let’s smash and together. Recall:

Recall:

\(x \in L \implies \exists y, V\qty(x,y) = 1\), \(x \not \in L \implies \forall y V\qty(x,y) = 0\)

\(x \in L \implies \text{Pr}\qty [V\qty(x,r) = 1] \geq \frac{2}{3}, x \not\in L \implies \text{Pr}\qty [V\qty(x,r) = 0] \geq \frac{2}{3}\)

Consider a new quantifier: