All reports by Author Abhranil Chatterjee:

__
TR19-063
| 28th April 2019
__

Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay#### Efficient Black-Box Identity Testing for Free Group Algebra

__
TR18-111
| 4th June 2018
__

Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay#### Beating Brute Force for Polynomial Identity Testing of General Depth-3 Circuits

Comments: 1

Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay

Hrubeš and Wigderson [HW14] initiated the study of

noncommutative arithmetic circuits with division computing a

noncommutative rational function in the free skew field, and

raised the question of rational identity testing. It is now known

that the problem can be solved in deterministic polynomial time in

more >>>

Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay

Let $C$ be a depth-3 $\Sigma\Pi\Sigma$ arithmetic circuit of size $s$,

computing a polynomial $f \in \mathbb{F}[x_1,\ldots, x_n]$ (where $\mathbb{F}$ = $\mathbb{Q}$ or

$\mathbb{C}$) with fan-in of product gates bounded by $d$. We give a

deterministic time $2^d \text{poly}(n,s)$ polynomial identity testing

algorithm to check whether $f \equiv 0$ or ...
more >>>