2 citations · 3 across the 5 of their papers we have counts for
4 papers · 1 filter
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…
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…
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…
Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
We give new and efficient black-box reconstruction algorithms for some classes of depth- arithmetic circuits. As a consequence, we obtain the first efficient algorithm for compu…