Bounds for Hardness Condensation in the Query Model

Chandrima Kayal, Rajat Mittal, Sai Soumya Nalli +4

For any Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ with a complexity measure having value $k\ll n$, is it possible to restrict the function $f$ to $\Theta (k)$ variables while keeping t…