Ilya Volkovich

According to our database, Ilya Volkovich authored at least 43 papers between 2008 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

Upper and Lower Bounds for the Linear Ordering Principle.

Edward A. Hirsch, Ilya Volkovich

CoRR, March, 2025

Communication Complexity of Equality and Error Correcting Codes.

Dale Jacobs, John Jeang, Vladimir Podolskii, Morgan E. Prior, Ilya Volkovich

Electron. Colloquium Comput. Complex., 2025

2024

Oblivious Classes Revisited: Lower Bounds and Hierarchies.

Karthik Gajulapalli, Zeyong Li, Ilya Volkovich

Electron. Colloquium Comput. Complex., 2024

Launching Identity Testing into (Bounded) Space.

Pranav Bisht, Nikhil Gupta, Prajakta Nimbhorkar, Ilya Volkovich

Electron. Colloquium Comput. Complex., 2024

Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies.

Karthik Gajulapalli, Zeyong Li, Ilya Volkovich

Proceedings of the 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2024

2023

Mutual Empowerment between Circuit Obfuscation and Circuit Minimization.

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

Electron. Colloquium Comput. Complex., 2023

Linear Independence, Alternants, and Applications.

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

New Characterization of the Factor Refinement Algorithm with Applications.

Aditya Ravi, Ilya Volkovich

Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation, 2023

Towards Identity Testing for Sums of Products of Read-Once and Multilinear Bounded-Read Formulae.

Pranav Bisht, Nikhil Gupta, Ilya Volkovich

Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

Synergy Between Circuit Obfuscation and Circuit Minimization.

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

Proceedings of the Approximation, 2023

2022

On Solving Sparse Polynomial Factorization Related Problems.

Pranav Bisht, Ilya Volkovich

Proceedings of the 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2022

2021

The Final Nail in the Coffin of Statistically-Secure Obfuscator.

Ilya Volkovich

Electron. Colloquium Comput. Complex., 2021

One-way Functions and Partial MCSP.

Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich

Electron. Colloquium Comput. Complex., 2021

Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits.

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Approximating the Number of Prime Factors Given an Oracle to Euler's Totient Function.

Yang Du, Ilya Volkovich

Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2021

One-Way Functions and a Conditional Variant of MKTP.

Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich

Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2021

2020

One (more) line on the most Ancient Algorithm in History.

Bruno Grenet, Ilya Volkovich

Proceedings of the 3rd Symposium on Simplicity in Algorithms, 2020

Reconstruction of Depth-4 Multilinear Circuits.

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

The Untold Story of SBP.

Ilya Volkovich

Proceedings of the Computer Science - Theory and Applications, 2020

The Power of Leibniz-Like Functions as Oracles.

Jaeyoon Kim, Ilya Volkovich, Nelson Xuzhi Zhang

Proceedings of the Computer Science - Theory and Applications, 2020

2019

The Complexity of Finding <i>S</i>-factors in Regular Graphs.

Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis

Electron. Colloquium Comput. Complex., 2019

The Complexity of Finding S-Factors in Regular Graphs.

Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis

Proceedings of the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2019

2018

A story of AM and Unique-SAT.

Ilya Volkovich

Electron. Colloquium Comput. Complex., 2018

One (more) line on the most Ancient Algorithm in History.

Ilya Volkovich

CoRR, 2018

Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree.

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

The Power of Natural Properties as Oracles.

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas.

Daniel Minahan, Ilya Volkovich

Proceedings of the 32nd Computational Complexity Conference, 2017

On Some Computations on Sparse Polynomials.

Ilya Volkovich

Proceedings of the Approximation, 2017

2016

Characterizing Arithmetic Read-Once Formulae.

Ilya Volkovich

ACM Trans. Comput. Theory, 2016

A Guide to Learning Arithmetic Circuits.

Ilya Volkovich

Proceedings of the 29th Conference on Learning Theory, 2016

2015

Computations beyond Exponentiation Gates and Applications.

Ilya Volkovich

Electron. Colloquium Comput. Complex., 2015

Deterministic polynomial identity tests for multilinear bounded-read formulae.

Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich

Comput. Complex., 2015

Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials.

Ilya Volkovich

Proceedings of the Approximation, 2015

2014

On Reconstruction and Testing of Read-Once Formulas.

Amir Shpilka, Ilya Volkovich

Theory Comput., 2014

Deterministically Factoring Sparse Polynomials into Multilinear Factors.

Ilya Volkovich

Electron. Colloquium Comput. Complex., 2014

On Learning, Lower Bounds and (un)Keeping Promises.

Ilya Volkovich

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2011

Polynomial identity testing and its relation to some algebraic problems.

Ilya Volkovich

PhD thesis, 2011

Black-box identity testing of depth-4 multilinear circuits.

Shubhangi Saraf, Ilya Volkovich

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae.

Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

2010

Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in.

Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors.

Amir Shpilka, Ilya Volkovich

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009

Improved Polynomial Identity Testing for Read-Once Formulas.

Amir Shpilka, Ilya Volkovich

Proceedings of the Approximation, 2009

2008

Read-once polynomial identity testing.

Amir Shpilka, Ilya Volkovich

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008