Computer Science Faculty
Ilya Volkovich
Assistant Professor
Ilya Volkovich
Ph.D.
Contact
245 Beacon Street 428F
Telephone: 617-552-3905
Email: ilya.volkovich@bc.edu
Education
- B.A., Technion, Israel Institute of Technology
- Ph.D., Technion, Israel Institute of Technology
Research Interests
Computational Complexity with Applications to Cryptography and Machine Learning.
In particular:
- Algebraic Complexity
- Randomness in Computation
- Computational Learning Theory
I am also interested in teaching Theory of Computation to undergraduate students
Department
SELECTED PUBLICATIONS
- “Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree”
Authors: Vishwas Bhargava, Shubhangi Saraf and Ilya Volkovich
JACM 2020 (Conference 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 Complexity of Finding S-factors in Regular Graphs”
Authors: Sanjana Kolisetty, Linh Le, Ilya Volkovich and Mihalis Yannakakis
FSTTCS 2019
- “Natural Oracles and Circuit Minimization”
Authors: Russell Impagliazzo, Valentine Kabanets and Ilya Volkovich
CCC 2018
- “Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas”
Authors: Daniel Minahan and Ilya Volkovich
ToCT 2018 (Conference version: CCC 2017)
- “Black-Box Identity Testing of Depth-4 Multilinear Circuits”
Authors: Shubhangi Saraf and Ilya Volkovich
Combinatorica 2018 (Conference version: STOC 2011)
- “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 (Conference version: CCC 2011)