Key points are not available for this paper at this time.
The range avoidance problem (denoted by Avoid) asks to find a string outside of the range of a given circuit C: 0, 1n→0, 1m, where m>n. Although at least half of the strings of length m are correct answers, it is not clear how to deterministically find one. Recent results of Korten (FOCS’21) and Ren, Wang, and Santhanam (FOCS’ 22) show that efficient deterministic algorithms for Avoid would have far-reaching consequences, including strong circuit lower bounds and explicit constructions of combinatorial objects (e. g. , Ramsey graphs, extractors, rigid matrices). This strongly motivates the question: does an efficient deterministic algorithm for Avoid actually exist?
Ilango et al. (Tue,) studied this question.