Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > RAJIT DATTA:
All reports by Author Rajit Datta:

TR19-063 | 28th April 2019
Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay

Efficient Black-Box Identity Testing for Free Group Algebra

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


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

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


TR17-074 | 29th April 2017
Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, Raja S

Efficient Identity Testing and Polynomial Factorization over Non-associative Free Rings

Revisions: 1

In this paper we study arithmetic computations over non-associative, and non-commutative free polynomials ring $\mathbb{F}\{x_1,x_2,\ldots,x_n\}$. Prior to this work, the non-associative arithmetic model of computation was considered by Hrubes, Wigderson, and Yehudayoff [HWY10]. They were interested in completeness and explicit lower bound results.

We focus on two main problems ... more >>>




ISSN 1433-8092 | Imprint