2 papers
cs.CC2026
Upper and Lower Bounds for the Linear Ordering Principle
Edward A. Hirsch, Ilya Volkovich
Korten and Pitassi (FOCS, 2024) defined a new complexity class as the polynomial-time Turing closure of the Linear Ordering Principle. They put it between (Merlin--Art…
cs.CC2025
A Note on Avoid vs MCSP
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…