3 papers
cs.CC2021
Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
We give new and efficient black-box reconstruction algorithms for some classes of depth- arithmetic circuits. As a consequence, we obtain the first efficient algorithm for compu…
math.AC2018
Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
In this paper we study the problem of deterministic factorization of sparse polynomials. We show that if is a polynomial with mono…
cs.DS2018
One (more) line on the most Ancient Algorithm in History
Bruno Grenet, Ilya Volkovich
We give a new simple and short ("one-line") analysis for the runtime of the well-known Euclidean Algorithm. While very short simple, the obtained upper bound in near-optimal.