Score: 0
A Note on Avoid vs MCSP
Published: December 25, 2025 |
arXiv ID: 2512.21764v1
By: Edward A. Hirsch, Ilya Volkovich
A recent result of Ghentiyala, Li, and Stephens-Davidowitz (ECCC TR 25-210) shows that any language reducible to the Range Avoidance Problem 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.
Similar Papers
86%
Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits
Computational Complexity
Makes it hard to prove some math statements are false.
18 Nov 2025
0
85%
Range Avoidance in Boolean Circuits via Turan-type Bounds
Computational Complexity
Makes computers solve hard problems faster.
21 Mar 2025
0
84%
Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
Computational Complexity
Makes computers solve harder problems faster.
29 Jul 2025
3