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 >>>

In this paper, we obtain several new results on lower bounds and derandomization for ACC^0 circuits (constant-depth circuits consisting of AND/OR/MOD_m gates for a fixed constant m, a frontier class in circuit complexity):

1. We prove that any polynomial-time Merlin-Arthur proof system with an ACC^0 verifier (denoted by ... 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 >>>

This paper studies the interaction of oracles with algorithmic approaches to proving circuit complexity lower bounds, establishing new results on two different kinds of questions.

1. We revisit some prominent open questions in circuit lower bounds, and provide a clean way of viewing them as circuit upper bound questions. Let ... more >>>

Kumar (CCC, 2023) used a novel switching lemma to prove exponential-size lower bounds for a circuit class GC^0 that not only contains AC^0 but can---with a single gate---compute functions that require exponential-size TC^0 circuits. Their main result was that switching-lemma lower bounds for AC^0 lift to GC^0 with no loss ... more >>>