All reports by Author Pushkar Joglekar:

__
TR22-042
| 31st March 2022
__

Vikraman Arvind, Pushkar Joglekar#### Matrix Polynomial Factorization via Higman Linearization

__
TR22-022
| 18th February 2022
__

Vikraman Arvind, Pushkar Joglekar#### On Efficient Noncommutative Polynomial Factorization via Higman Linearization

Revisions: 3

__
TR17-087
| 9th May 2017
__

Pushkar Joglekar, Raghavendra Rao B V, Sidhartha Sivakumar#### On Weak-Space Complexity over Complex Numbers

__
TR16-193
| 22nd November 2016
__

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

__
TR15-141
| 26th August 2015
__

Pushkar Joglekar, Aravind N.R.#### On the expressive power of read-once determinants

__
TR15-124
| 3rd August 2015
__

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

Revisions: 1

__
TR15-004
| 4th January 2015
__

Vikraman Arvind, Pushkar Joglekar, Gaurav Rattan#### On the Complexity of Noncommutative Polynomial Factorization

__
TR09-073
| 6th September 2009
__

Vikraman Arvind, Pushkar Joglekar, Srikanth Srinivasan#### On Lower Bounds for Constant Width Arithmetic Circuits

__
TR09-026
| 17th February 2009
__

Vikraman Arvind, Pushkar Joglekar#### Arithmetic Circuit Size, Identity Testing, and Finite Automata

Vikraman Arvind, Pushkar Joglekar

In continuation to our recent work on noncommutative

polynomial factorization, we consider the factorization problem for

matrices of polynomials and show the following results.

\begin{itemize}

\item Given as input a full rank $d\times d$ matrix $M$ whose entries

$M_{ij}$ are polynomials in the free noncommutative ring

more >>>

Vikraman Arvind, Pushkar Joglekar

In this paper we study the problem of efficiently factorizing polynomials in the free noncommutative ring F of polynomials in noncommuting variables x_1,x_2,…,x_n over the field F. We obtain the following result:

Given a noncommutative arithmetic formula of size s computing a noncommutative polynomial f in F as input, where ... more >>>

Pushkar Joglekar, Raghavendra Rao B V, Sidhartha Sivakumar

Defining a feasible notion of space over the Blum-Shub-Smale (BSS) model of algebraic computation is a long standing open problem. In an attempt to define a right notion of space complexity for the BSS model, Naurois [CiE, 2007] introduced the notion of weak-space. We investigate the weak-space bounded computations and ... 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 >>>

Pushkar Joglekar, Aravind N.R.

We introduce and study the notion of read-$k$ projections of the determinant: a polynomial $f \in \mathbb{F}[x_1, \ldots, x_n]$ is called a {\it read-$k$ projection of determinant} if $f=det(M)$, where entries of matrix $M$ are either field elements or variables such that each variable appears at most $k$ times in ... 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 >>>

Vikraman Arvind, Pushkar Joglekar, Gaurav Rattan

In this paper we study the complexity of factorization of polynomials in the free noncommutative ring $\mathbb{F}\langle x_1,x_2,\ldots,x_n\rangle$ of polynomials over the field $\mathbb{F}$ and noncommuting variables $x_1,x_2,\ldots,x_n$. Our main results are the following.

Although $\mathbb{F}\langle x_1,\dots,x_n \rangle$ is not a unique factorization ring, we note that variable-disjoint factorization in ... more >>>

Vikraman Arvind, Pushkar Joglekar, Srikanth Srinivasan

The motivation for this paper is to study the complexity of constant-width arithmetic circuits. Our main results are the following.

1. For every k > 1, we provide an explicit polynomial that can be computed by a linear-sized monotone circuit of width 2k but has no subexponential-sized monotone circuit ...
more >>>

Vikraman Arvind, Pushkar Joglekar

Let $\F\{x_1,x_2,\cdots,x_n\}$ be the noncommutative polynomial

ring over a field $\F$, where the $x_i$'s are free noncommuting

formal variables. Given a finite automaton $\A$ with the $x_i$'s as

alphabet, we can define polynomials $\f( mod A)$ and $\f(div A)$

obtained by natural operations that we ...
more >>>