Meta-Complexity Seminar

Join Meta-Complexity program participants in this weekly seminar.

Speaker: Rahul Ilango

Title: Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic

Abstract: The Circuit Range Avoidance Problem (denoted Avoid) asks to find a string outside of the range of a given circuit C mapping n-bits to m-bits 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?

In this work, we prove under the existence of subexponentially secure indistinguishability obfuscation (iO) that deterministic polynomial-time algorithms for Avoid imply NP=coNP. Combining this with Jain, Lin, and Sahai's recent breakthrough construction of iO from well-founded assumptions (STOC'21, EUROCRYPT'22), we provide the first plausible evidence that Avoid has no efficient deterministic algorithm.

Extending our techniques, we prove a surprising separation in bounded arithmetic, conditioned on similar assumptions. Assuming subexponentially secure iO and coNP is not infinitely often in AM, we show that Avoid has no deterministic polynomial-time algorithm even when one is allowed O(1) queries to an oracle that can invert the given input circuit on an arbitrarily chosen m-bit string. It follows that the dual Weak Pigeonhole Principle is not provable in Cook's theory PV_1. This gives (under plausible assumptions) the first separation of Cook's theory PV_1 for polynomial-time reasoning and Jeˇrábek's theory APC_1 for probabilistic polynomial-time reasoning.

Based on joint work with Jiatu Li and Ryan Williams.