Ilya Volkovich

79 papers A* 8A 5B 1Misc 2Journal 48Unranked 14
YearRankTypeTitle / Venue / Authors
2026 J jnl
Linear Independence, Alternants and Applications.
SIAM J. Comput.
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2026 A conf
Upper and Lower Bounds for the Linear Ordering Principle.
STACS
Edward A. Hirsch, Ilya Volkovich
2026 J jnl
Yet Another Proof that $BPP \subseteq PH$.
Electron. Colloquium Comput. Complex.
Ilya Volkovich
2026 — conf
Yet Another Proof that BPP ⊆ PH.
SOSA
Ilya Volkovich
2025 J jnl
A Note on Avoid vs MCSP.
CoRR
Edward A. Hirsch, Ilya Volkovich
2025 J jnl
A Note on Avoid vs MCSP.
Electron. Colloquium Comput. Complex.
Edward A. Hirsch, Ilya Volkovich
2025 J jnl
Communication Complexity of Equality and Error Correcting Codes.
Electron. Colloquium Comput. Complex.
Dale Jacobs, John Jeang, Vladimir Podolskii, Morgan E. Prior, Ilya Volkovich
2025 — conf
Communication Complexity of Equality and Error-Correcting Codes.
FSTTCS
Dale Jacobs, John Jeang, Vladimir Podolskii, Morgan E. Prior, Ilya Volkovich
2025 J jnl
Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies.
CoRR
Karthik Gajulapalli, Zeyong Li, Ilya Volkovich
2025 J jnl
On Solving Sparse Polynomial Factorization Related Problems.
Comput. Complex.
Pranav Bisht, Ilya Volkovich
2025 J jnl
Reconstruction of Depth-4 Multilinear Circuits.
ACM Trans. Comput. Theory
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2025 J jnl
Upper and Lower Bounds for the Linear Ordering Principle.
CoRR
Edward A. Hirsch, Ilya Volkovich
2025 J jnl
Upper and Lower Bounds for the Linear Ordering Principle.
Electron. Colloquium Comput. Complex.
Edward A. Hirsch, Ilya Volkovich
2024 J jnl
Launching Identity Testing into (Bounded) Space.
Electron. Colloquium Comput. Complex.
Pranav Bisht, Nikhil Gupta, Prajakta Nimbhorkar, Ilya Volkovich
2024 J jnl
Oblivious Classes Revisited: Lower Bounds and Hierarchies.
Electron. Colloquium Comput. Complex.
Karthik Gajulapalli, Zeyong Li, Ilya Volkovich
2024 — conf
Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies.
FSTTCS
Karthik Gajulapalli, Zeyong Li, Ilya Volkovich
2023 J jnl
Linear Independence, Alternants and Applications.
Electron. Colloquium Comput. Complex.
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2023 A* conf
Linear Independence, Alternants, and Applications.
STOC
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2023 J jnl
Mutual Empowerment between Circuit Obfuscation and Circuit Minimization.
Electron. Colloquium Comput. Complex.
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
2023 B conf
New Characterization of the Factor Refinement Algorithm with Applications.
ISSAC
Aditya Ravi, Ilya Volkovich
2023 A conf
Synergy Between Circuit Obfuscation and Circuit Minimization.
APPROX/RANDOM
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
2023 J jnl
The Power of Natural Properties as Oracles.
Comput. Complex.
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
2023 J jnl
The final nail in the coffin of statistically-secure obfuscator.
Inf. Process. Lett.
Ilya Volkovich
2023 — conf
Towards Identity Testing for Sums of Products of Read-Once and Multilinear Bounded-Read Formulae.
FSTTCS
Pranav Bisht, Nikhil Gupta, Ilya Volkovich
2023 J jnl
Towards Identity Testing for Sums of Products of Read-Once and Multilinear Bounded-Read Formulae.
Electron. Colloquium Comput. Complex.
Pranav Bisht, Nikhil Gupta, Ilya Volkovich
2022 — conf
On Solving Sparse Polynomial Factorization Related Problems.
FSTTCS
Pranav Bisht, Ilya Volkovich
2022 J jnl
On Solving Sparse Polynomial Factorization Related Problems.
Electron. Colloquium Comput. Complex.
Pranav Bisht, Ilya Volkovich
2021 — conf
Approximating the Number of Prime Factors Given an Oracle to Euler's Totient Function.
FSTTCS
Yang Du, Ilya Volkovich
2021 — conf
One-Way Functions and a Conditional Variant of MKTP.
FSTTCS
Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich
2021 J jnl
One-way Functions and Partial MCSP.
Electron. Colloquium Comput. Complex.
Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich
2021 J jnl
Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits.
CoRR
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2021 J jnl
Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits.
Electron. Colloquium Comput. Complex.
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2021 A* conf
Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits.
STOC
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2021 J jnl
The Final Nail in the Coffin of Statistically-Secure Obfuscator.
Electron. Colloquium Comput. Complex.
Ilya Volkovich
2020 J jnl
Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree.
J. ACM
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2020 — conf
One (more) line on the most Ancient Algorithm in History.
SOSA
Bruno Grenet, Ilya Volkovich
2020 A* conf
Reconstruction of Depth-4 Multilinear Circuits.
SODA
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2020 Misc conf
The Power of Leibniz-Like Functions as Oracles.
CSR
Jaeyoon Kim, Ilya Volkovich, Nelson Xuzhi Zhang
2020 Misc conf
The Untold Story of SBP.
CSR
Ilya Volkovich
2019 J jnl
Reconstruction of Depth-$4$ Multilinear Circuits.
Electron. Colloquium Comput. Complex.
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2019 J jnl
The Complexity of Finding
Electron. Colloquium Comput. Complex.
Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis
2019 — conf
The Complexity of Finding S-Factors in Regular Graphs.
FSTTCS
Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis
2018 J jnl
A story of AM and Unique-SAT.
Electron. Colloquium Comput. Complex.
Ilya Volkovich
2018 J jnl
Black-Box Identity Testing of Depth-4 Multilinear Circuits.
Comb.
Shubhangi Saraf, Ilya Volkovich
2018 J jnl
Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas.
ACM Trans. Comput. Theory
Daniel Minahan, Ilya Volkovich
2018 A* conf
Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree.
FOCS
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2018 J jnl
Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree.
CoRR
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2018 J jnl
Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree.
Electron. Colloquium Comput. Complex.
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2018 J jnl
One (more) line on the most Ancient Algorithm in History.
CoRR
Ilya Volkovich
2018 A conf
The Power of Natural Properties as Oracles.
CCC
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
2017 A conf
Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas.
CCC
Daniel Minahan, Ilya Volkovich
2017 — conf
On Some Computations on Sparse Polynomials.
APPROX-RANDOM
Ilya Volkovich
2017 J jnl
The Power of Natural Properties as Oracles.
Electron. Colloquium Comput. Complex.
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
2016 A* conf
A Guide to Learning Arithmetic Circuits.
COLT
Ilya Volkovich
2016 J jnl
Characterizing Arithmetic Read-Once Formulae.
ACM Trans. Comput. Theory
Ilya Volkovich
2016 J jnl
Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas.
Electron. Colloquium Comput. Complex.
Daniel Minahan, Ilya Volkovich
2015 J jnl
A Guide to Learning Arithmetic Circuits.
Electron. Colloquium Comput. Complex.
Ilya Volkovich
2015 J jnl
Computations beyond Exponentiation Gates and Applications.
Electron. Colloquium Comput. Complex.
Ilya Volkovich
2015 J jnl
Deterministic polynomial identity tests for multilinear bounded-read formulae.
Comput. Complex.
Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich
2015 — conf
Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials.
APPROX-RANDOM
Ilya Volkovich
2015 J jnl
Read-once polynomial identity testing.
Comput. Complex.
Amir Shpilka, Ilya Volkovich
2014 J jnl
Characterizing Arithmetic Read-Once Formulae.
CoRR
Ilya Volkovich
2014 J jnl
Deterministically Factoring Sparse Polynomials into Multilinear Factors.
Electron. Colloquium Comput. Complex.
Ilya Volkovich
2014 — conf
On Learning, Lower Bounds and (un)Keeping Promises.
ICALP (1)
Ilya Volkovich
2014 J jnl
On Learning, Lower Bounds and (un)Keeping Promises.
Electron. Colloquium Comput. Complex.
Ilya Volkovich
2014 J jnl
On Reconstruction and Testing of Read-Once Formulas.
Theory Comput.
Amir Shpilka, Ilya Volkovich
2013 J jnl
Deterministic Identity Testing of Depth-4 Multilinear Circuits with Bounded Top Fan-in.
SIAM J. Comput.
Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich
2011 J jnl
Black-Box Identity Testing of Depth-4 Multilinear Circuits.
Electron. Colloquium Comput. Complex.
Shubhangi Saraf, Ilya Volkovich
2011 A* conf
Black-box identity testing of depth-4 multilinear circuits.
STOC
Shubhangi Saraf, Ilya Volkovich
2011 A conf
Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae.
CCC
Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich
2011 — —
Polynomial identity testing and its relation to some algebraic problems.
Ilya Volkovich
2010 J jnl
Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae.
Electron. Colloquium Comput. Complex.
Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich
2010 A* conf
Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in.
STOC
Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich
2010 — conf
On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors.
ICALP (1)
Amir Shpilka, Ilya Volkovich
2010 J jnl
On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors.
Electron. Colloquium Comput. Complex.
Amir Shpilka, Ilya Volkovich
2010 J jnl
Read-Once Polynomial Identity Testing.
Electron. Colloquium Comput. Complex.
Amir Shpilka, Ilya Volkovich
2009 J jnl
Deterministic identity testing of depth 4 multilinear circuits with bounded top fan-in.
Electron. Colloquium Comput. Complex.
Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich
2009 — conf
Improved Polynomial Identity Testing for Read-Once Formulas.
APPROX-RANDOM
Amir Shpilka, Ilya Volkovich
2008 A* conf
Read-once polynomial identity testing.
STOC
Amir Shpilka, Ilya Volkovich