Ilya Volkovich
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Ilya Volkovich has a total of 13 co-authors. Here are the top co-authors by number of shared publications:
- Vishwas Bhargava
California Institute of Technology, Pasadena, CA 91125 USA
3 shared publications - Shubhangi Saraf
University of Toronto, Toronto, Canada
2 shared publications - Aditya Ravi
University of Michigan, USA
1 shared publication - Bruno Grenet
LIRMM Univ. Montpellier CNRS Montpellier France
1 shared publication - Edward A. Hirsch
Department of Computer Science Ariel University Israel
1 shared publication Jaeyoon Kim
University of Michigan
1 shared publication
Latest Publications
- 9 January 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 55 (1) , 28-64
Linear Independence, Alternants and Applications
We develop a new technique for analyzing linear independence of multivariate polynomials. One of our main technical contributions is a Small Witness for Linear Independence lemma which states the following. If the polynomials [Formula: see text] over [Formula: see text] are [Formula: see text]-linearly independent then there exists a subset [Formula: see text] of size at most [Formula: see text] such that [Formula: see text] are also [Formula: see text]-linearly independent. We show how to effectively combine this lemma with the use of the alternant matrix to analyze linear independence of polynomials. We also give applications of our technique to the questions of polynomial identity testing and arithmetic circuit reconstruction. (1) We give a general technique for lifting efficient polynomial identity testing algorithms from basic classes of circuits, satisfying some closure properties, to more general classes of circuits. As one of the corollaries of this result, we obtain the first algorithm for polynomial identity testing for depth-4, constant-occur circuits that works over all fields. This strengthens a result by M. Agrawal, C. Saha, R. Saptharishi, and N. Saxena [ SIAM J. Comput., 45 (2016), pp. 1533–1562] that works in the case when the characteristic is 0 or sufficiently large. Another corollary is an identity testing algorithm for a special case of depth-5 circuits. To the best of our knowledge, this is the first algorithm for this class of circuits. (2) We give new and efficient black-box reconstruction algorithms for the class of set-multilinear depth-3 circuits of constant top fan-in, where the set-multilinear variable partition is unknown. This generalizes the results of V. Bhargava, S. Saraf, and I. Volkovich [STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021, pp. 809–822] and S. Peleg, A. Shpilka, and B. Volk [15th Innovations in Theoretical Computer Science Conference, ITCS 2024, pp. 87:1–87:20] which work in the case of known variable partition, and correspond to tensor decomposition of constant-rank tensors.
- 9 January 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 55 (1) , 28-64
Linear Independence, Alternants and Applications
We develop a new technique for analyzing linear independence of multivariate polynomials. One of our main technical contributions is a Small Witness for Linear Independence lemma which states the following. If the polynomials [Formula: see text] over [Formula: see text] are [Formula: see text]-linearly independent then there exists a subset [Formula: see text] of size at most [Formula: see text] such that [Formula: see text] are also [Formula: see text]-linearly independent. We show how to effectively combine this lemma with the use of the alternant matrix to analyze linear independence of polynomials. We also give applications of our technique to the questions of polynomial identity testing and arithmetic circuit reconstruction. (1) We give a general technique for lifting efficient polynomial identity testing algorithms from basic classes of circuits, satisfying some closure properties, to more general classes of circuits. As one of the corollaries of this result, we obtain the first algorithm for polynomial identity testing for depth-4, constant-occur circuits that works over all fields. This strengthens a result by M. Agrawal, C. Saha, R. Saptharishi, and N. Saxena [ SIAM J. Comput., 45 (2016), pp. 1533–1562] that works in the case when the characteristic is 0 or sufficiently large. Another corollary is an identity testing algorithm for a special case of depth-5 circuits. To the best of our knowledge, this is the first algorithm for this class of circuits. (2) We give new and efficient black-box reconstruction algorithms for the class of set-multilinear depth-3 circuits of constant top fan-in, where the set-multilinear variable partition is unknown. This generalizes the results of V. Bhargava, S. Saraf, and I. Volkovich [STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021, pp. 809–822] and S. Peleg, A. Shpilka, and B. Volk [15th Innovations in Theoretical Computer Science Conference, ITCS 2024, pp. 87:1–87:20] which work in the case of known variable partition, and correspond to tensor decomposition of constant-rank tensors.
- Open Access
A Note on Avoid vs MCSP
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 $\cap$ coAM. In this note, we present a different potential avenue for obtaining the same result via the Minimal Circuit Size Problem.Open AccessA Note on Avoid vs MCSP
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 $\cap$ coAM. In this note, we present a different potential avenue for obtaining the same result via the Minimal Circuit Size Problem. - Open Access
Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies
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 input. In particular, we study the connections between the symmetric polynomial time $\mathsf{S_2P}$ and its oblivious counterpart $\mathsf{O_2P}$. Among our results, we construct an explicit language in $\mathsf{O_2P}$ that cannot be computed by circuits of size $n^k$, and thus prove a hierarchy theorem for $\mathsf{O_2TIME}$. Along the way we also make partial progress towards the resolution of an open question posed by Goldreich and Meir (TOCT 2015) that relates the complexity of $\mathsf{NP}$ to its oblivious counterpart $\mathsf{ONP}$. To the best of our knowledge, these results constitute the first explicit fixed-polynomial lower bound and hierarchy theorem for $\mathsf{O_2P}$. The smallest uniform complexity class for which such lower bounds were previously known was $\mathsf{S_2P}$, due to Cai (JCSS 2007). In addition, this is the first uniform hierarchy theorem for a semantic class. All previous results required some non-uniformity.Open AccessOblivious Complexity Classes Revisited: Lower Bounds and Hierarchies
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 input. In particular, we study the connections between the symmetric polynomial time $\mathsf{S_2P}$ and its oblivious counterpart $\mathsf{O_2P}$. Among our results, we construct an explicit language in $\mathsf{O_2P}$ that cannot be computed by circuits of size $n^k$, and thus prove a hierarchy theorem for $\mathsf{O_2TIME}$. Along the way we also make partial progress towards the resolution of an open question posed by Goldreich and Meir (TOCT 2015) that relates the complexity of $\mathsf{NP}$ to its oblivious counterpart $\mathsf{ONP}$. To the best of our knowledge, these results constitute the first explicit fixed-polynomial lower bound and hierarchy theorem for $\mathsf{O_2P}$. The smallest uniform complexity class for which such lower bounds were previously known was $\mathsf{S_2P}$, due to Cai (JCSS 2007). In addition, this is the first uniform hierarchy theorem for a semantic class. All previous results required some non-uniformity. - 1 June 2025
- Published by Springer Nature in computational complexity
- Vol. 34 (1) , 1-65
On Solving Sparse Polynomial Factorization Related Problems
- 1 June 2025
- Published by Springer Nature in computational complexity
- Vol. 34 (1) , 1-65
On Solving Sparse Polynomial Factorization Related Problems
- Open Access
- 28 March 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
Reconstruction of Depth-4 Multilinear Circuits
We present a deterministic algorithm for reconstructing multilinear ΣΠΣΠ ( k ) circuits, i.e. multilinear depth-4 circuits with fan-in k at the top + gate. For any fixed k , given black-box access to a polynomial \(f \in \mathbb {F}[x_{1},x_{2},\ldots,x_{n} ] \) computable by a multilinear ΣΠΣΠ ( k ) circuit of size s , the algorithm runs in time quasi-poly( \(n,s,|\mathbb {F}|) \) and outputs a multilinear ΣΠΣΠ ( k ) circuit of size quasi-poly( n , s ) that computes f . Our result solves an open problem posed in [GKL12] (STOC, 2012). Indeed, prior to our work, efficient reconstruction algorithms for multilinear ΣΠΣΠ ( k ) circuits were known only for the case of k = 2 [GKL12,Vol17].- 28 March 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
Open AccessReconstruction of Depth-4 Multilinear Circuits
We present a deterministic algorithm for reconstructing multilinear ΣΠΣΠ ( k ) circuits, i.e. multilinear depth-4 circuits with fan-in k at the top + gate. For any fixed k , given black-box access to a polynomial \(f \in \mathbb {F}[x_{1},x_{2},\ldots,x_{n} ] \) computable by a multilinear ΣΠΣΠ ( k ) circuit of size s , the algorithm runs in time quasi-poly( \(n,s,|\mathbb {F}|) \) and outputs a multilinear ΣΠΣΠ ( k ) circuit of size quasi-poly( n , s ) that computes f . Our result solves an open problem posed in [GKL12] (STOC, 2012). Indeed, prior to our work, efficient reconstruction algorithms for multilinear ΣΠΣΠ ( k ) circuits were known only for the case of k = 2 [GKL12,Vol17]. - Open Access
- 24 July 2023
- Published by Association for Computing Machinery (ACM)
- p. 490-497
New Characterization of the Factor Refinement Algorithm with Applications
- 24 July 2023
- Published by Association for Computing Machinery (ACM)
- p. 490-497
Open AccessNew Characterization of the Factor Refinement Algorithm with Applications
- 6 July 2023
- Published by Springer Nature in computational complexity
- Vol. 32 (2) , 1-40
The Power of Natural Properties as Oracles
- 6 July 2023
- Published by Springer Nature in computational complexity
- Vol. 32 (2) , 1-40
The Power of Natural Properties as Oracles
- 10 February 2023
- Published by Elsevier in Information Processing Letters
- Vol. 182
The final nail in the coffin of statistically-secure obfuscator
- 10 February 2023
- Published by Elsevier in Information Processing Letters
- Vol. 182
The final nail in the coffin of statistically-secure obfuscator
- 22 June 2020
- Published by Springer Nature
- p. 393-405
The Untold Story of $\mathsf {SBP}$