Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > PUSHKAR JOGLEKAR:
All reports by Author Pushkar Joglekar:

TR17-087 | 9th May 2017
Pushkar Joglekar, Raghavendra Rao B V, Sidhartha Sivakumar

On Weak-Space Complexity over Complex Numbers

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


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


TR15-141 | 26th August 2015
Pushkar Joglekar, Aravind N.R.

On the expressive power of read-once determinants

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


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


TR15-004 | 4th January 2015
Vikraman Arvind, Pushkar Joglekar, Gaurav Rattan

On the Complexity of Noncommutative Polynomial Factorization

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


TR09-073 | 6th September 2009
Vikraman Arvind, Pushkar Joglekar, Srikanth Srinivasan

On Lower Bounds for Constant Width Arithmetic Circuits

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


TR09-026 | 17th February 2009
Vikraman Arvind, Pushkar Joglekar

Arithmetic Circuit Size, Identity Testing, and Finite Automata

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




ISSN 1433-8092 | Imprint