All reports by Author Vishwas Bhargava:

__
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 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 >>>