The Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP) are the fundamental algorithmic questions in the geometry of numbers. In the past two decades, their algorithmic complexity has been studied quite extensively due to their connection with lattice based cryptosystems. In this paper, we study these problems in ... more >>>

We consider read-$k$ determinantal representations of polynomials and prove some non-expressibility results. A square matrix $M$ whose entries are variables or field elements will be called \emph{read-$k$}, if every variable occurs at most $k$ times in $M$. It will be called a \emph{determinantal representation} of a polynomial $f$ if $f=\det(M)$. ... more >>>

We study the \emph{noncommutative rank} problem, $\NCRANK$, of computing the rank of matrices with linear entries in $n$ noncommuting variables and the problem of \emph{noncommutative Rational Identity Testing}, $\RIT$, which is to decide if a given rational formula in $n$ noncommuting variables is zero on its domain of definition.

... more >>>

Based on a theorem of Bergman we show that multivariate noncommutative polynomial factorization is deterministic polynomial-time reducible to the factorization of bivariate noncommutative polynomials. More precisely, we show the following:

(1) In the white-box setting, given an n-variate noncommutative polynomial f in F over a field F (either a ... more >>>

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

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

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

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

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

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

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

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

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