All reports by Author Hanlin Ren:

__
TR22-048
| 4th April 2022
__

Hanlin Ren, Rahul Santhanam, Zhikun Wang#### On the Range Avoidance Problem for Circuits

Hanlin Ren, Rahul Santhanam, Zhikun Wang

We consider the range avoidance problem (called Avoid): given the description of a circuit $C:\{0, 1\}^n \to \{0, 1\}^\ell$ (where $\ell > n$), find a string $y\in\{0, 1\}^\ell$ that is not in the range of $C$. This problem is complete for the class APEPP that corresponds to explicit constructions of ... more >>>