Abstract

The Range Avoidance (Avoid) problem is defined as follows: given an expanding circuit , find a that is not in the range of C. Intuitively, C maps N pigeons to 2N pigeonholes, and we are looking for an empty pigeonhole. The exact complexity of Avoid has attracted a lot of attention in theoretical computer science in recent years due to its close connection to explicit constructions: the task of constructing many important combinatorial objects such as Ramsey graphs, rigid matrices and two-source extractors reduces to that of solving Avoid.

We show that Avoid is provably not NP-hard (assuming that the Polynomial Hierarchy does not collapse). More generally, any decision problem efficiently reducible to Avoid is contained in AM intersect coAM. Underlying our proof is an Arthur-Merlin type algorithm that solves Avoid and a novel AM protocol for upper bounding the size of the image of any given circuit.

This talk is based on a recent paper, joint with Surendra Ghentiyala and Noah Stephens-Davidowitz, to appear in STOC 2026.

Time

2026-05-13  14:00 - 15:00

Speaker

Zeyong Li, National University of Singapore

Room

Room 104