Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR19-104 | 6th August 2019
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

Reconstruction of Depth-$4$ Multilinear Circuits

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

TR18-130 | 16th July 2018
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree

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

TR17-016 | 31st January 2017
Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal, Nitin Saxena

Irreducibility and deterministic r-th root finding over finite fields

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

ISSN 1433-8092 | Imprint