All reports by Author Raja S:

__
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

__
TR16-193
| 22nd November 2016
__

Vikraman Arvind, Pushkar Joglekar, Partha Mukhopadhyay, Raja S#### Identity Testing for +-Regular Noncommutative Arithmetic Circuits

__
TR16-089
| 2nd June 2016
__

Vikraman Arvind, Partha Mukhopadhyay, Raja S#### Randomized Polynomial Time Identity Testing for Noncommutative Circuits

Revisions: 2

__
TR15-176
| 6th November 2015
__

Vikraman Arvind, Raja S#### Some Lower Bound Results for Set-Multilinear Arithmetic Computations

Revisions: 1

__
TR15-124
| 3rd August 2015
__

Vikraman Arvind, Pushkar Joglekar, Raja S#### Noncommutative Valiant's Classes: Structure and Complete Problems

Revisions: 1

Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, Raja S

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

Vikraman Arvind, Pushkar Joglekar, Partha Mukhopadhyay, Raja S

An efficient randomized polynomial identity test for noncommutative

polynomials given by noncommutative arithmetic circuits remains an

open problem. The main bottleneck to applying known techniques is that

a noncommutative circuit of size $s$ can compute a polynomial of

degree exponential in $s$ with a double-exponential number of nonzero

monomials. ...
more >>>

Vikraman Arvind, Partha Mukhopadhyay, Raja S

In this paper we show that polynomial identity testing for

noncommutative circuits of size $s$, computing a polynomial in

$\mathbb{F}\langle z_1,z_2,\cdots,z_n \rangle$, can be done by a randomized algorithm

with running time polynomial in $s$ and $n$. This answers a question

that has been open for over ten years.

The ... more >>>

Vikraman Arvind, Raja S

In this paper, we study the structure of set-multilinear arithmetic

circuits and set-multilinear branching programs with the aim of

showing lower bound results. We define some natural restrictions of

these models for which we are able to show lower bound results. Some

of our results extend existing lower bounds, while ...
more >>>

Vikraman Arvind, Pushkar Joglekar, Raja S

In this paper we explore the noncommutative analogues, $\mathrm{VP}_{nc}$ and

$\mathrm{VNP}_{nc}$, of Valiant's algebraic complexity classes and show some

striking connections to classical formal language theory. Our main

results are the following:

(1) We show that Dyck polynomials (defined from the Dyck languages of formal language theory) are complete for ... more >>>