Ilya Volkovich

Publication Activity (10 Years)

Years Active: 2008-2024
Publications (10 Years): 47

Top Topics

Matrix Decomposition

Top Venues

Electron. Colloquium Comput. Complex.

Comput. Complex.

Publications

Karthik Gajulapalli, Zeyong Li, Ilya Volkovich
Oblivious Classes Revisited: Lower Bounds and Hierarchies. Electron. Colloquium Comput. Complex. (2024)
Pranav Bisht, Nikhil Gupta, Prajakta Nimbhorkar, Ilya Volkovich
Launching Identity Testing into (Bounded) Space. Electron. Colloquium Comput. Complex. (2024)
Pranav Bisht, Nikhil Gupta, Ilya Volkovich
Towards Identity Testing for Sums of Products of Read-Once and Multilinear Bounded-Read Formulae. FSTTCS (2023)
Aditya Ravi, Ilya Volkovich
New Characterization of the Factor Refinement Algorithm with Applications. ISSAC (2023)
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
The Power of Natural Properties as Oracles. Comput. Complex. 32 (2) (2023)
Ilya Volkovich
The final nail in the coffin of statistically-secure obfuscator. Inf. Process. Lett. 182 (2023)
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
Synergy Between Circuit Obfuscation and Circuit Minimization. APPROX/RANDOM (2023)
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
Linear Independence, Alternants and Applications. Electron. Colloquium Comput. Complex. (2023)
Pranav Bisht, Nikhil Gupta, Ilya Volkovich
Towards Identity Testing for Sums of Products of Read-Once and Multilinear Bounded-Read Formulae. Electron. Colloquium Comput. Complex. (2023)
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
Linear Independence, Alternants, and Applications. STOC (2023)
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
Mutual Empowerment between Circuit Obfuscation and Circuit Minimization. Electron. Colloquium Comput. Complex. (2023)
Pranav Bisht, Ilya Volkovich
On Solving Sparse Polynomial Factorization Related Problems. Electron. Colloquium Comput. Complex. (2022)
Pranav Bisht, Ilya Volkovich
On Solving Sparse Polynomial Factorization Related Problems. FSTTCS (2022)
Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich
One-way Functions and Partial MCSP. Electron. Colloquium Comput. Complex. 28 (2021)
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits. CoRR (2021)
Ilya Volkovich
The Final Nail in the Coffin of Statistically-Secure Obfuscator. Electron. Colloquium Comput. Complex. 28 (2021)
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits. Electron. Colloquium Comput. Complex. 28 (2021)
Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich
One-Way Functions and a Conditional Variant of MKTP. FSTTCS (2021)
Yang Du, Ilya Volkovich
Approximating the Number of Prime Factors Given an Oracle to Euler's Totient Function. FSTTCS (2021)
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits. STOC (2021)
Jaeyoon Kim, Ilya Volkovich, Nelson Xuzhi Zhang
The Power of Leibniz-Like Functions as Oracles. CSR (2020)
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree. J. ACM 67 (2) (2020)
Ilya Volkovich
The Untold Story of SBP. CSR (2020)
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
Reconstruction of Depth-4 Multilinear Circuits. SODA (2020)
Bruno Grenet, Ilya Volkovich
One (more) line on the most Ancient Algorithm in History. SOSA (2020)
Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis
The Complexity of Finding {$S$}-factors in Regular Graphs. Electron. Colloquium Comput. Complex. 26 (2019)
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
Reconstruction of Depth-$4$ Multilinear Circuits. Electron. Colloquium Comput. Complex. 26 (2019)
Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis
The Complexity of Finding S-Factors in Regular Graphs. FSTTCS (2019)
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree. Electron. Colloquium Comput. Complex. 25 (2018)
Ilya Volkovich
A story of AM and Unique-SAT. Electron. Colloquium Comput. Complex. 25 (2018)
Shubhangi Saraf, Ilya Volkovich
Black-Box Identity Testing of Depth-4 Multilinear Circuits. Comb. 38 (5) (2018)
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
The Power of Natural Properties as Oracles. Computational Complexity Conference (2018)
Daniel Minahan, Ilya Volkovich
Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas. ACM Trans. Comput. Theory 10 (3) (2018)
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree. FOCS (2018)
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree. CoRR (2018)
Ilya Volkovich
One (more) line on the most Ancient Algorithm in History. CoRR (2018)
Daniel Minahan, Ilya Volkovich
Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas. Computational Complexity Conference (2017)
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
The Power of Natural Properties as Oracles. Electron. Colloquium Comput. Complex. 24 (2017)
Ilya Volkovich
On Some Computations on Sparse Polynomials. APPROX-RANDOM (2017)
Ilya Volkovich
Characterizing Arithmetic Read-Once Formulae. ACM Trans. Comput. Theory 8 (1) (2016)
Daniel Minahan, Ilya Volkovich
Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas. Electron. Colloquium Comput. Complex. 23 (2016)
Ilya Volkovich
A Guide to Learning Arithmetic Circuits. COLT (2016)
Amir Shpilka, Ilya Volkovich
Read-once polynomial identity testing. Comput. Complex. 24 (3) (2015)
Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich
Deterministic polynomial identity tests for multilinear bounded-read formulae. Comput. Complex. 24 (4) (2015)
Ilya Volkovich
A Guide to Learning Arithmetic Circuits. Electron. Colloquium Comput. Complex. 22 (2015)
Ilya Volkovich
Computations beyond Exponentiation Gates and Applications. Electron. Colloquium Comput. Complex. 22 (2015)
Ilya Volkovich
Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials. APPROX-RANDOM (2015)
Ilya Volkovich
On Learning, Lower Bounds and (un)Keeping Promises. ICALP (1) (2014)
Ilya Volkovich
Characterizing Arithmetic Read-Once Formulae. CoRR (2014)
Ilya Volkovich
On Learning, Lower Bounds and (un)Keeping Promises. Electron. Colloquium Comput. Complex. 21 (2014)
Amir Shpilka, Ilya Volkovich
On Reconstruction and Testing of Read-Once Formulas. Theory Comput. 10 (2014)
Ilya Volkovich
Deterministically Factoring Sparse Polynomials into Multilinear Factors. Electron. Colloquium Comput. Complex. 21 (2014)
Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich
Deterministic Identity Testing of Depth-4 Multilinear Circuits with Bounded Top Fan-in. SIAM J. Comput. 42 (6) (2013)
Shubhangi Saraf, Ilya Volkovich
Black-Box Identity Testing of Depth-4 Multilinear Circuits. Electron. Colloquium Comput. Complex. 18 (2011)
Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich
Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae. Computational Complexity Conference (2011)
Shubhangi Saraf, Ilya Volkovich
Black-box identity testing of depth-4 multilinear circuits. STOC (2011)
Amir Shpilka, Ilya Volkovich
On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors. ICALP (1) (2010)
Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich
Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae. Electron. Colloquium Comput. Complex. 17 (2010)
Amir Shpilka, Ilya Volkovich
Read-Once Polynomial Identity Testing. Electron. Colloquium Comput. Complex. 17 (2010)
Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich
Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in. STOC (2010)
Amir Shpilka, Ilya Volkovich
On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors. Electron. Colloquium Comput. Complex. 17 (2010)
Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich
Deterministic identity testing of depth 4 multilinear circuits with bounded top fan-in. Electron. Colloquium Comput. Complex. 16 (2009)
Amir Shpilka, Ilya Volkovich
Improved Polynomial Identity Testing for Read-Once Formulas. APPROX-RANDOM (2009)
Amir Shpilka, Ilya Volkovich
Read-once polynomial identity testing. STOC (2008)