2 citations · 3 across the 5 of their papers we have counts for
7 papers
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…
Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
In this paper we study the problem of deterministic factorization of sparse polynomials. We show that if is a polynomial with mono…
One (more) line on the most Ancient Algorithm in History
Bruno Grenet, Ilya Volkovich
We give a new simple and short ("one-line") analysis for the runtime of the well-known Euclidean Algorithm. While very short simple, the obtained upper bound in near-optimal.
Characterizing Arithmetic Read-Once Formulae
Ilya Volkovich
An \emph{arithmetic read-once formula} (ROF for short) is a formula (i.e. a tree of computation) in which the operations are and such that every input variable label…