All reports by Author Vishwas Bhargava:

__
TR23-032
| 24th March 2023
__

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich#### Linear Independence, Alternants and Applications

__
TR22-063
| 30th April 2022
__

Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Mrinal Kumar, Chris Umans#### Fast Multivariate Multipoint Evaluation Over All Finite Fields

__
TR21-162
| 14th November 2021
__

Vishwas Bhargava, Sumanta Ghosh, Mrinal Kumar, Chandra Kanta Mohapatra#### Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications

Revisions: 3

__
TR21-155
| 13th November 2021
__

Vishwas Bhargava, Ankit Garg, Neeraj Kayal, Chandan Saha#### Learning generalized depth-three arithmetic circuits in the non-degenerate case

Revisions: 1

__
TR21-062
| 29th April 2021
__

Vishwas Bhargava, Sumanta Ghosh#### Improved Hitting Set for Orbit of ROABPs

Revisions: 2

__
TR21-045
| 22nd March 2021
__

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich#### Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits

__
TR19-104
| 6th August 2019
__

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich#### Reconstruction of Depth-$4$ Multilinear Circuits

__
TR18-130
| 16th July 2018
__

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich#### Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree

__
TR17-016
| 31st January 2017
__

Vishwas Bhargava, GĂˇbor Ivanyos, Rajat Mittal, Nitin Saxena#### Irreducibility and deterministic r-th root finding over finite fields

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 \emph{Small Witness for Linear Independence} (SWLI) lemma which states the following.

If the polynomials $f_1,f_2, \ldots, f_k \in \F[X]$ over $X=\{x_1, \ldots, x_n\}$ are $\F$-linearly independent then there exists ...
more >>>

Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Mrinal Kumar, 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 $\mathbb{F}$ that outputs the evaluations of an $m$-variate polynomial of ... more >>>

Vishwas Bhargava, Sumanta Ghosh, Mrinal Kumar, 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 is also closely related to fast algorithms for other natural ... more >>>

Vishwas Bhargava, Ankit Garg, Neeraj Kayal, Chandan Saha

Consider a homogeneous degree $d$ polynomial $f = T_1 + \cdots + T_s$, $T_i = g_i(\ell_{i,1}, \ldots, \ell_{i, m})$ where $g_i$'s are homogeneous $m$-variate degree $d$ polynomials and $\ell_{i,j}$'s are linear polynomials in $n$ variables. We design a (randomized) learning algorithm that given black-box access to $f$, computes black-boxes for ... more >>>

Vishwas Bhargava, Sumanta Ghosh

The orbit of an $n$-variate polynomial $f(\mathbf{x})$ over a field $\mathbb{F}$ is the set $\{f(A \mathbf{x} + b)\,\mid\, A\in \mathrm{GL}({n,\mathbb{F}})\mbox{ and }\mathbf{b} \in \mathbb{F}^n\}$, and the orbit of a polynomial class is the union of orbits of all the polynomials in it. In this paper, we give improved constructions of ... more >>>

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 {\it constant-rank} tensor. ... more >>>

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

We present a deterministic algorithm for reconstructing multilinear $\Sigma\Pi\Sigma\Pi(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 \in \mathbb{F}[x_{1},x_{2},\ldots ,x_{n}]$ computable by a multilinear $\Sigma\Pi\Sigma\Pi(k)$ circuit of size $s$, the algorithm runs in time ... more >>>

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

In this paper we study the problem of deterministic factorization of sparse polynomials. We show that if $f \in \mathbb{F}[x_{1},x_{2},\ldots ,x_{n}]$ is a 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 ... more >>>

Vishwas Bhargava, GĂˇbor Ivanyos, Rajat Mittal, Nitin Saxena

Constructing $r$-th nonresidue over a finite field is a fundamental computational problem. A related problem is to construct an irreducible polynomial of degree $r^e$ (where $r$ is a prime) over a given finite field $\F_q$ of characteristic $p$ (equivalently, constructing the bigger field $\F_{q^{r^e}}$). Both these problems have famous randomized ... more >>>