Using \epsilon-bias spaces over F_2 , we show that the Remote Point Problem (RPP), introduced by Alon et al [APY09], has an NC^2 algorithm (achieving the same parameters as [APY09]). We study a generalization of the Remote Point Problem to groups: we replace F_n by G^n for an arbitrary fixed ... more >>>

We investigate the power of Algebraic Branching Programs (ABPs) augmented with help polynomials, and constant-depth Boolean circuits augmented with help functions. We relate the problem of proving explicit lower bounds in both these models to the Remote Point Problem (introduced by Alon, Panigrahy, and Yekhanin (RANDOM '09)). More precisely, proving ... more >>>

The *range avoidance problem*, denoted as \mathcal{C}-\rm Avoid, asks to find a non-output of a given \mathcal{C}-circuit C:\{0,1\}^n\to\{0,1\}^\ell with stretch \ell>n. This problem has recently received much attention in complexity theory for its connections with circuit lower bounds and other explicit construction problems. Inspired by the Algorithmic Method for circuit ... 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 >>>