2025/12/25 by Edward Hirsch, Hirsch, Edward A., Ilya Volkovich +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #68Q15 #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #DNA and Biological Computing #F.1.3 #FOS: Computer and information sciences #semigroups and automata theory
paper · doi:10.48550/arxiv.2512.21764
openalex publication_date 2025/12/25 · openalex created_date 2025/12/30 · openalex updated_date 2026/07/28
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 ∩ coAM. In this note, we present a different potential avenue for obtaining the same result via the Minimal Circuit Size Problem.