Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR16-193 | 22nd November 2016
Vikraman Arvind, Pushkar Joglekar, Partha Mukhopadhyay, Raja S

Identity Testing for +-Regular Noncommutative Arithmetic Circuits

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

TR16-089 | 2nd June 2016
Vikraman Arvind, Partha Mukhopadhyay, Raja S

Randomized Polynomial Time Identity Testing for Noncommutative Circuits

Revisions: 2

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

TR15-176 | 6th November 2015
Vikraman Arvind, Raja S

Some Lower Bound Results for Set-Multilinear Arithmetic Computations

Revisions: 1

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

TR15-124 | 3rd August 2015
Vikraman Arvind, Pushkar Joglekar, Raja S

Noncommutative Valiant's Classes: Structure and Complete Problems

Revisions: 1

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

ISSN 1433-8092 | Imprint