Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Abhranil Chatterjee:

TR22-067 | 4th May 2022
Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay

Black-box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial-time

Hrube\v{s} and Wigderson (2015) initiated the complexity-theoretic study of noncommutative formulas with inverse gates. They introduced the Rational Identity Testing (RIT) problem which is to decide whether a noncommutative rational formula computes zero in the free skew field. In the white-box setting, deterministic polynomial-time algorithms are known for this problem ... more >>>

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

ISSN 1433-8092 | Imprint