“Research is formalized curiosity. It is poking and prying with a purpose.”
― Zora Neale Hurston
(As is customary in theoretical computer science, the author ordering on the papers is alphabetical)
“Towards Identity Testing for Sums of Products of Read-Once and Multilinear Bounded-Read Formulae”
Authors: Pranav Bisht, Nikhil Gupta and Ilya Volkovich
FSTTCS 2023
“Synergy between Circuit Obfuscation and Circuit Minimization”
Authors: Russell Impagliazzo, Valentine Kabanets and Ilya Volkovich
RANDOM 2023
“Linear Independence, Alternants and Applications”
Authors: Vishwas Bhargava, Shubhangi Saraf and Ilya Volkovich
STOC 2023
“The Final Nail in the Coffin of Statistically-Secure Obfuscator”
Author: Ilya Volkovich
IPL 2023
“New Characterization of the Factor Refinement Algorithm with Applications”
Authors: Aditya Ravi and Ilya Volkovich
ISSAC 2023
“The Power of Natural Properties as Oracles”
Authors: Russell Impagliazzo, Valentine Kabanets and Ilya Volkovich
CC 2022 (Preliminary version: CCC 2018)
“On Solving Sparse Polynomial Factorization Related Problems”
Authors: Pranav Bisht and Ilya Volkovich
FSTTCS 2022
“Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits”
Authors: Vishwas Bhargava, Shubhangi Saraf and Ilya Volkovich
STOC 2021
“One-way Functions and a Conditional Variant of MKTP”
Authors: Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala and Ilya Volkovich
FSTTCS 2021
“Approximating the Number of Prime Factors Given an Oracle to Euler’s Totient Function”
Authors: Yang Du and Ilya Volkovich
FSTTCS 2021
“Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree”
Authors: Vishwas Bhargava, Shubhangi Saraf and Ilya Volkovich
JACM 2020 (Preliminary version: FOCS 2018)
“Reconstruction of Depth-4 Multilinear Circuits“
Authors: Vishwas Bhargava, Shubhangi Saraf and Ilya Volkovich
SODA 2020
“One (more) line on the most Ancient Algorithm in History”
Authors: Bruno Grenet and Ilya Volkovich
SOSA 2020
“The Power of Leibniz-Like Functions as Oracles”
Authors: Jaeyoon Kim, Ilya Volkovich and Nelson Xuzhi Zhang
CSR 2020
“The Untold Story of SBP”
Author: Ilya Volkovich
CSR 2020
“The Complexity of Finding S-factors in Regular Graphs”
Authors: Sanjana Kolisetty, Linh Le, Ilya Volkovich and Mihalis Yannakakis
FSTTCS 2019
“Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas”
Authors: Daniel Minahan and Ilya Volkovich
ToCT 2018 (Preliminary version: CCC 2017)
“Black-Box Identity Testing of Depth-4 Multilinear Circuits”
Authors: Shubhangi Saraf and Ilya Volkovich
Combinatorica 2018 (Preliminary version: STOC 2011)
“On some Computations on Sparse Polynomials”
Author: Ilya Volkovich
RANDOM 2017
“Characterizing Arithmetic Read-Once Formulae”
Author: Ilya Volkovich
ToCT 2016
“A Guide to Learning Arithmetic Circuits”
Author: Ilya Volkovich
COLT 2016
“Derandomizing Polynomial Identity Testing for Constant-Read Multilinear Formulae”
Authors: Matthew Anderson, Dieter van Melkebeek and Ilya Volkovich
CC 2015 (Preliminary version: CCC 2011)
“Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials”
Author: Ilya Volkovich
RANDOM 2015
“Read-Once Polynomial Identity Testing”
Authors: Amir Shpilka and Ilya Volkovich
CC 2015 (Containing PIT Algorithms from “Read-once Polynomial Identity Testing”, STOC 2008 and “Improved Polynomial Identity Testing for Read-once Formulas”, RANDOM-APPROX 2009)
“On Learning, Lower Bounds and (un)Keeping Promises”
Author: Ilya Volkovich
ICALP 2014
“On Reconstruction and Testing Read-Once Formulas”
Authors: Amir Shpilka and Ilya Volkovich
ToC 2014 (Partially based on “Read-once Polynomial Identity Testing”, STOC 2008)
“Deterministic Identity Testing of Depth-4 Multilinear Circuits with Bounded Top Fan-in”
Authors: Zohar S. Karnin, Partha Mukhppadhyay, Amir Shpilka and Ilya Volkovich
SICOMP 2013 (Preliminary version: STOC 2010)
“Polynomial Identity Testing and its relation to Algebraic problems”
Author: Ilya Volkovich
Ph.D. Thesis, Technion, Israel Institute of Technology, Haifa, Israel, 2012.
“On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors”
Authors: Amir Shpilka and Ilya Volkovich
ICALP 2010