All reports by Author Abhranil Chatterjee:

__
TR24-073
| 11th April 2024
__

Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay#### Trading Determinism for Noncommutativity in Edmonds' Problem

__
TR23-147
| 27th September 2023
__

Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay#### Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time

Revisions: 5
,
Comments: 1

__
TR23-122
| 9th August 2023
__

Vikraman Arvind, Abhranil Chatterjee#### On Lifting Lower Bounds for Noncommutative Circuits using Automata

__
TR23-115
| 8th August 2023
__

Abhranil Chatterjee, Mrinal Kumar, Ben Lee Volk#### Determinants vs. Algebraic Branching Programs

Revisions: 1

__
TR23-075
| 17th May 2023
__

Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj#### Border Complexity of Symbolic Determinant under Rank One Restriction

__
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

__
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, Partha Mukhopadhyay

Let $X=X_1\sqcup X_2\sqcup\ldots\sqcup X_k$ be a partitioned set of variables such that the variables in each part $X_i$ are noncommuting but for any $i\neq j$, the variables $x \in X_i$ commute with the variables $x' \in X_j$. Given as input a square matrix $T$ whose entries are linear forms over ... more >>>

Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay

Rational Identity Testing (RIT) is the decision problem of determining whether or not a given noncommutative rational formula computes zero in the free skew field. It admits a deterministic polynomial-time white-box algorithm [Garg et al., 2016; Ivanyos et al., 2018; Hamada and Hirai, 2021], and a randomized polynomial-time black-box algorithm ... more >>>

Vikraman Arvind, Abhranil Chatterjee

We revisit the main result of Carmosino et al \cite{CILM18} which shows that an $\Omega(n^{\omega/2+\epsilon})$ size noncommutative arithmetic circuit size lower bound (where $\omega$ is the matrix multiplication exponent) for a constant-degree $n$-variate polynomial family $(g_n)_n$, where each $g_n$ is a noncommutative polynomial, can be ``lifted'' to an exponential size ... more >>>

Abhranil Chatterjee, Mrinal Kumar, Ben Lee Volk

We show that for every homogeneous polynomial of degree $d$, if it has determinantal complexity at most $s$, then it can be computed by a homogeneous algebraic branching program (ABP) of size at most $O(d^5s)$. Moreover, we show that for \textit{most} homogeneous polynomials, the width of the resulting homogeneous ABP ... more >>>

Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj

VBP is the class of polynomial families that can be computed by the determinant of a symbolic matrix of the form $A_0 + \sum_{i=1}^n A_ix_i$ where the size of each $A_i$ is polynomial in the number of variables (equivalently, computable by polynomial-sized algebraic branching programs (ABP)). A major open problem ... more >>>

Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay

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

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