Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-220 | 25th December 2025 20:15

A Note on Avoid vs MCSP

RSS-Feed




TR25-220
Authors: Edward Hirsch, Ilya Volkovich
Publication: 28th December 2025 07:30
Downloads: 45
Keywords: 


Abstract:

A recent result of Ghentiyala, Li, and Stephens-Davidowitz (ECCC TR 25-210) shows that any language reducible to the Range Avoidance Problem (Avoid) via deterministic or randomized Turing reductions is contained in AM $\cap$ coAM. In this note, we present a different potential avenue for obtaining the same result via the Minimal Circuit Size Problem (MCSP).



ISSN 1433-8092 | Imprint