Deterministic Circuit Range Avoidance is (Likely) Intractable

Circuit Range Avoidance (denoted Avoid) is a computational problem where, given a Boolean circuit with more output bits than input bits, one must output a string outside of the range of the circuit. A simple counting argument implies that such a string must always exist and also guarantees that outputting a uniformly random string is correct with good probability. A natural question is whether this can be derandomized: does there exist an efficient deterministic algorithm for Avoid? We give the first evidence that deterministically solving Avoid is intractable. We show that there is no polynomial-time algorithm for Avoid under plausible assumptions in complexity theory and cryptography. Specifically, our assumptions are that NP ≠ coNP and that subexponentially-secure indistinguishability obfuscation exists.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2025

Author dc:creator

• Ilango, Rahul

Advisor dc:contributor.advisor

• Williams, Ryan

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright retained by author(s)

Licence dc:rights.uri

• https://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/164654

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/164654