Given a circuit $G: \{0, 1\}^n \to \{0, 1\}^m$ with $m > n$, the *range avoidance* problem ($\text{Avoid}$) asks to output a string $y\in \{0, 1\}^m$ that is not in the range of $G$. Besides its profound connection to circuit complexity and explicit construction problems, this problem is also related ... more >>>

The Range Avoidance ($\text{Avoid}$) problem $\mathcal{C}$-$\text{Avoid}[n,m(n)]$ asks that, given a circuit in a class $\mathcal{C}$ with input length $n$ and output length $m(n)>n$, find a string not in the range of the circuit. This problem has been a central piece in several recent frameworks of proving circuit lower bounds and ... more >>>

Affine extractors give some of the best-known lower bounds for various computational models, such as AC$^0$ circuits, parity decision trees, and general Boolean circuits. However, they are not known to give strong lower bounds for read-once branching programs (ROBPs). In a recent work, Gryaznov, Pudl\'{a}k, and Talebanfard (CCC' 22) introduced ... more >>>