Vishwas Bhargava

STOC Conference 2023 Conference Paper

Linear Independence, Alternants, and Applications

• Vishwas Bhargava
• Shubhangi Saraf
• Ilya Volkovich

We develop a new technique for analyzing linear independence of multivariate polynomials. One of our main technical contributions is a Small Witness for Linear Independence (SWLI) lemma which states the following. If the polynomials f 1 , f 2 , …, f k ∈ F [ X ] over X ={ x 1 , …, x n } are F -linearly independent then there exists a subset S ⊆ X of size at most k −1 such that f 1 , f 2 , …, f k are also F ( X ∖ S )-linearly independent.

FOCS Conference 2022 Conference Paper

Fast Multivariate Multipoint Evaluation Over All Finite Fields

• Vishwas Bhargava
• Sumanta Ghosh
• Zeyu Guo 0001
• Mrinal Kumar 0001
• Chris Umans

Multivariate multipoint evaluation is the problem of evaluating a multivariate polynomial, given as a coefficient vector, simultaneously at multiple evaluation points. In this work, we show that there exists a deterministic algorithm for multivariate multipoint evaluation over any finite field F that outputs the evaluations of an m-variate polynomial of degree less than d in each variable at N points in time $(d^{m}+N)^{1+o(1)}$ poly $(m, \ d, \ \log|\mathbb{F}|)$ for all $m\in \mathbb{N}$ and all sufficiently large $d\in \mathbb{N}$. A previous work of Kedlaya and Umans (FOCS 2008, SICOMP 2011) achieved the same time complexity when the number of variables m is at most $d^{o(1)}$ and had left the problem of removing this condition as an open problem. A recent work of Bhargava, Ghosh, Kumar and Mohapatra (STOC 2022) answered this question when the underlying field is not too large and has characteristic less than $d^{o(1)}$. In this work, we remove this constraint on the number of variables over all finite fields, thereby answering the question of Kedlaya and Umans over all finite fields. Our algorithm relies on a non-trivial combination of ideas from three seemingly different previously known algorithms for multivariate multipoint evaluation, namely the algorithms of Kedlaya and Umans, that of Björklund, Kaski and Williams (IPEC 2017, Algorithmica 2019), and that of Bhargava, Ghosh, Kumar and Mohapatra, together with a result of Bombieri and Vinogradov from analytic number theory about the distribution of primes in an arithmetic progression. We also present a second algorithm for multivariate multipoint evaluation that is completely elementary and in particular, avoids the use of the Bombieri-Vinogradov Theorem. However, it requires a mild assumption that the field size is bounded by an exponential-tower in d of bounded height.

STOC Conference 2022 Conference Paper

Fast, algebraic multivariate multipoint evaluation in small characteristic and applications

• Vishwas Bhargava
• Sumanta Ghosh
• Mrinal Kumar 0001
• Chandra Kanta Mohapatra

Multipoint evaluation is the computational task of evaluating a polynomial given as a list of coefficients at a given set of inputs. Besides being a natural and fundamental question in computer algebra on its own, fast algorithms for this problem are also closely related to fast algorithms for other natural algebraic questions like polynomial factorization and modular composition. And while nearly linear time algorithms have been known for the univariate instance of multipoint evaluation for close to five decades due to a work of Borodin and Moenck, fast algorithms for the multivariate version have been much harder to come by. In a significant improvement to the state of art for this problem, Umans and Kedlaya & Umans gave nearly linear time algorithms for this problem over field of small characteristic and over all finite fields respectively, provided that the number of variables n is at most d o (1) where the degree of the input polynomial in every variable is less than d . They also stated the question of designing fast algorithms for the large variable case (i.e. n ∉ d o (1) ) as an open problem.

STOC Conference 2021 Conference Paper

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-3 arithmetic circuits. As a consequence, we obtain the first efficient algorithm for computing the tensor rank and for finding the optimal tensor decomposition as a sum of rank-one tensors when then input is a constant-rank tensor. More specifically, we provide efficient learning algorithms that run in randomized polynomial time over general fields and in deterministic polynomial time over and for the following classes: 1) Set-multilinear depth- 3 circuits of constant top fan-in ( ( k ) circuits) . As a consequence of our algorithm, we obtain the first polynomial time algorithm for tensor rank computation and optimal tensor decomposition of constant-rank tensors. This result holds for d dimensional tensors for any d , but is interesting even for d =3. 2) Sums of powers of constantly many linear forms ( ( k ) circuits) . As a consequence we obtain the first polynomial-time algorithm for tensor rank computation and optimal tensor decomposition of constant-rank symmetric tensors. 3) Multilinear depth-3 circuits of constant top fan-in (multilinear ( k ) circuits) . Our algorithm works over all fields of characteristic 0 or large enough characteristic. Prior to our work the only efficient algorithms known were over polynomially-sized finite fields (see. Karnin-Shpilka 09’). Prior to our work, the only polynomial-time or even subexponential-time algorithms known (deterministic or randomized) for subclasses of ( k ) circuits that also work over large/infinite fields were for the setting when the top fan-in k is at most 2 (see Sinha 16’ and Sinha 20’).

SODA Conference 2020 Conference Paper

Reconstruction of Depth-4 Multilinear Circuits

• Vishwas Bhargava
• Shubhangi Saraf
• Ilya Volkovich

We present a deterministic algorithm for reconstructing multilinear ƩпƩп( k ) circuits, i. e. multilinear depth-4 circuits with fan-in k at the top + gate. For any fixed k, given black-box access to a polynomial f ϵ 픽[ x 1, x 2, …, x n ] computable by a multilinear ƩпƩп( k ) circuit of size s, the algorithm runs in time quasi-poly( n, s, |픽|) and outputs a multilinear ƩпƩп( k ) circuit of size quasi-poly( n, s ) that computes f. Our result solves an open problem posed in [15] (STOC, 2012). Indeed, prior to our work, efficient reconstruction algorithms for multilinear ƩпƩп( k ) circuits were known only for the case of k = 2 [15, 52].

SODA Conference 2019 Conference Paper

A Deterministic PTAS for the Algebraic Rank of Bounded Degree Polynomials

• Vishwas Bhargava
• Markus Bläser
• Gorav Jindal
• Anurag Pandey 0001

FOCS Conference 2018 Conference Paper

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 f is an n-variate polynomial with s monomials, with individual degrees of its variables bounded by d, then f can be deterministically factored in time s poly(d) log n. Prior to our work, the only efficient factoring algorithms known for this class of polynomials were randomized, and other than for the cases of d = 1 and d = 2, only exponential time deterministic factoring algorithms were known. A crucial ingredient in our proof is a quasi-polynomial sparsity bound for factors of sparse polynomials of bounded individual degree. In particular we show if f is an s-sparse polynomial in n variables, with individual degrees of its variables bounded by d, then the sparsity of each factor of f is bounded by s O(d2 log n). This is the first nontrivial bound on factor sparsity for d > 2. Our sparsity bound uses techniques from convex geometry, such as the theory of Newton polytopes and an approximate version of the classical Caratheodory's Theorem. Our work addresses and partially answers a question of von zur Gathen and Kaltofen (JCSS 1985) who asked whether a quasi-polynomial bound holds for the sparsity of factors of sparse polynomials.