1 citations · 1 across the 1 of their papers we have counts for
3 papers
cs.CC2026★ 1 cited
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…
cs.CC2025
Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies
Karthik Gajulapalli, Zeyong Li, Ilya Volkovich
In this work we study oblivious complexity classes. These classes capture the power of interactive proofs where the prover(s) are only given the input size rather than the actual i…