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

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Noncommutative Valiant's Classes: Structure and Complete Problems

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 the class $\mathrm{VP}_{nc}$ under $\le_{abp}$ reductions. Likewise, it turns out that $\mathrm{PAL}$ (Palindrome polynomials defined from palindromes) are complete for the class $\mathrm{VSKEW}_{nc}$ (defined by polynomial-size skew circuits) under $\le_{abp}$ reductions. The proof of these results is by suitably adapting the classical Chomsky-Schützenberger theorem showing that Dyck languages are the hardest CFLs. (2) Next, we consider the class $\mathrm{VNP}_{nc}$ . It is known~\cite{HWY10a} that, assuming the sum-of-squares conjecture, the noncommutative polynomial $\sum_{w\in\{x_0,x_1\}^n}ww$ requires exponential size circuits. We unconditionally show that $\sum_{w\in\{x_0,x_1\}^n}ww$ is not $\mathrm{VNP}_{nc}$ -complete under the projection reducibility. As a consequence, assuming the sum-of-squares conjecture, we exhibit a strictly infinite hierarchy of p-families under projections inside $\mathrm{VNP}_{nc}$ (analogous to Ladner's theorem~\cite{Ladner75}). In the final section we discuss some new $\mathrm{VNP}_{nc}$ -complete problems under $\le_{abp}$ -reductions. (3) Inside $\mathrm{VP}_{nc}$ too we show there is a strict hierarchy of p-families (based on the nesting depth of Dyck polynomials) under the $\le_{abp}$ reducibility.

preprint2015arXiv

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,\dots,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,x_2,\dots,x_n \rangle$ is not a unique factorization ring, we note that variable-disjoint factorization in $\mathbb{F}\langle x_1,x_2,\dots,x_n \rangle$ has the uniqueness property. Furthermore, we prove that computing the variable-disjoint factorization is polynomial-time equivalent to Polynomial Identity Testing (both when the input polynomial is given by an arithmetic circuit or an algebraic branching program). We also show that variable-disjoint factorization in the black-box setting can be efficiently computed (where the factors computed will be also given by black-boxes, analogous to the work [KT91] in the commutative setting). As a consequence of the previous result we show that homogeneous noncommutative polynomials and multilinear noncommutative polynomials have unique factorizations in the usual sense, which can be efficiently computed. Finally, we discuss a polynomial decomposition problem in $\mathbb{F}\langle x_1,x_2,\dots,x_n\rangle$ which is a natural generalization of homogeneous polynomial factorization and prove some complexity bounds for it.

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.