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
- 鈥淒eterministic Factorization of Sparse Polynomials with Bounded Individual Degree鈥�
Authors:听 Vishwas Bhargava, Shubhangi Saraf and Ilya Volkovich
JACM 2020 (Conference version: FOCS 2018)
- 鈥淩econstruction of Depth-4 Multilinear Circuits鈥�
Authors:听 Vishwas Bhargava, Shubhangi Saraf and Ilya Volkovich
SODA 2020
- 鈥淥ne (more) line on the most Ancient Algorithm in History鈥�
Authors: Bruno Grenet and Ilya Volkovich
SOSA 2020
- 鈥淭he Complexity of Finding S-factors in Regular Graphs鈥�
Authors:听 Sanjana Kolisetty, Linh Le, Ilya Volkovich and Mihalis Yannakakis
FSTTCS 2019
- 鈥淣atural Oracles and Circuit Minimization鈥�
Authors:听 Russell Impagliazzo, Valentine Kabanets and Ilya Volkovich
CCC 2018
- 鈥淐omplete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas鈥�
Authors: Daniel Minahan and Ilya Volkovich
ToCT 2018 (Conference version: CCC 2017)
- 鈥淏lack-Box Identity Testing of Depth-4 Multilinear Circuits鈥�
Authors: Shubhangi Saraf and Ilya Volkovich
Combinatorica 2018 (Conference version: STOC 2011)
- 鈥淎 Guide to Learning Arithmetic Circuits鈥�
Author: Ilya Volkovich
COLT 2016
- 鈥淒erandomizing Polynomial Identity Testing for Constant-Read Multilinear Formulae鈥�
Authors: Matthew Anderson, Dieter van Melkebeek and Ilya Volkovich
CC 2015 (Conference version: CCC 2011)
听