We prove that, for every constant $\varepsilon>0$ and every function $f:\Sigma^n\to\{0, 1\}$, there is a coalition of $O(n/\sqrt{\log n})$ coordinates and a target output $b\in\{0, 1\}$ such that, after the remaining coordinates are sampled uniformly and independently, the coalition can choose its values to make the output equal to $b$ ... more >>>

We prove that for all $\varepsilon>0$, there exists a positive integer $k$ such that given a $4$-to-$1$ Game $\Psi$ with alphabet size at most $k$, it is NP-hard to distinguish between the case that val$(\Psi)=1$ and the case that val$(\Psi)\leq \delta$. This confirms the $4$-to-$1$ Games Conjecture from [Khot, CCC ... more >>>

We use this framework to construct HSGs for read-once CNFs and read-once CNFs with parities. For formulas on $n$ variables with density at least $\varepsilon$, our generators use $O(\log(n/\varepsilon))$ seed bits. This bound is optimal up to a constant factor. Applying the hitting reduction of Gopalan, Meka, Reingold, Trevisan, and ... more >>>