Source author record

Pushkar S. Joglekar

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity

Catalog footprint

Research overview

2works

1topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Matrix Polynomial Factorization via Higman Linearization

In continuation to our recent work on noncommutative polynomial factorization, we consider the factorization problem for matrices of polynomials and show the following results. (1) Given as input a full rank $d\times d$ matrix $M$ whose entries $M_{ij}$ are polynomials in the free noncommutative ring $\mathbb{F}_q\langle x_1,x_2,\ldots,x_n \rangle$ , where each $M_{ij}$ is given by a noncommutative arithmetic formula of size at most $s$ , we give a randomized algorithm that runs in time polynomial in $d,s, n$ and $\log_2q$ that computes a factorization of $M$ as a matrix product $M=M_1M_2\cdots M_r$ , where each $d\times d$ matrix factor $M_i$ is irreducible (in a well-defined sense) and the entries of each $M_i$ are polynomials in $\mathbb{F}_q \langle x_1,x_2,\ldots,x_n \rangle$ that are output as algebraic branching programs. We also obtain a deterministic algorithm for the problem that runs in $poly(d,n,s,q)$ . (2)A special case is the efficient factorization of matrices whose entries are univariate polynomials in $\mathbb{F}[x]$ . When $\mathbb{F}$ is a finite field the above result applies. When $\mathbb{F}$ is the field of rationals we obtain a deterministic polynomial-time algorithm for the problem.

preprint2015arXiv

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 $M$ . A monomial set $S$ is said to be expressible as read- $k$ projection of determinant if there is a read- $k$ projection of determinant $f$ such that the monomial set of $f$ is equal to $S$ . We obtain basic results relating read- $k$ determinantal projections to the well-studied notion of determinantal complexity. We show that for sufficiently large $n$ , the $n \times n$ permanent polynomial $Perm_n$ and the elementary symmetric polynomials of degree $d$ on $n$ variables $S_n^d$ for $2 \leq d \leq n-2$ are not expressible as read-once projection of determinant, whereas $mon(Perm_n)$ and $mon(S_n^d)$ are expressible as read-once projections of determinant. We also give examples of monomial sets which are not expressible as read-once projections of determinant.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.