Search Results

Documents authored by Joglekar, Pushkar S.

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.14
A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results

Authors: Vikraman Arvind and Pushkar S. Joglekar

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We study the noncommutative rank problem, ncRANK, of computing the rank of matrices with linear entries in n noncommuting variables and the problem of 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. Motivated by the question whether these problems have deterministic NC algorithms, we revisit their interrelationship from a parallel complexity point of view. We show the following results: 1) Based on Cohn’s embedding theorem [Cohn, 1990; Cohn, 2006] we show deterministic NC reductions from multivariate ncRANK to bivariate ncRANK and from multivariate RIT to bivariate RIT. 2) We obtain a deterministic NC-Turing reduction from bivariate RIT to bivariate ncRANK, thereby proving that a deterministic NC algorithm for bivariate ncRANK would imply that both multivariate RIT and multivariate ncRANK are in deterministic NC.
Cite as

Vikraman Arvind and Pushkar S. Joglekar. A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.ICALP.2024.14,
  author =	{Arvind, Vikraman and Joglekar, Pushkar S.},
  title =	{{A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{14:1--14:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.14},
  URN =		{urn:nbn:de:0030-drops-201571},
  doi =		{10.4230/LIPIcs.ICALP.2024.14},
  annote =	{Keywords: noncommutative rank, rational formulas, identity testing, parallel complexity}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.14
Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization

Authors: Vikraman Arvind and Pushkar S. Joglekar

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Based on a theorem of Bergman [Cohn, 2006] 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 ∈ 𝔽⟨X⟩ over a field 𝔽 (either a finite field or the rationals) as an arithmetic circuit (or algebraic branching program), computing a complete factorization of f into irreducible factors is deterministic polynomial-time reducible to white-box factorization of a noncommutative bivariate polynomial g ∈ 𝔽⟨x,y⟩; the reduction transforms f into a circuit for g (resp. ABP for g), and given a complete factorization of g (namely, arithmetic circuits (resp. ABPs) for irreducible factors of g) the reduction recovers a complete factorization of f in polynomial time. We also obtain a similar deterministic polynomial-time reduction in the black-box setting. 2) Additionally, we show over the field of rationals that bivariate linear matrix factorization of 4× 4 matrices is at least as hard as factoring square-free integers. This indicates that reducing noncommutative polynomial factorization to linear matrix factorization (as done in [Vikraman Arvind and Pushkar S. Joglekar, 2022]) is unlikely to succeed over the field of rationals even in the bivariate case. In contrast, multivariate linear matrix factorization for 3×3 matrices over rationals is in polynomial time.
Cite as

Vikraman Arvind and Pushkar S. Joglekar. Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.MFCS.2023.14,
  author =	{Arvind, Vikraman and Joglekar, Pushkar S.},
  title =	{{Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{14:1--14:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.14},
  URN =		{urn:nbn:de:0030-drops-185480},
  doi =		{10.4230/LIPIcs.MFCS.2023.14},
  annote =	{Keywords: Arithmetic circuits, algebraic branching programs, polynomial factorization, automata, noncommutative polynomial ring}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.12
On Efficient Noncommutative Polynomial Factorization via Higman Linearization

Authors: Vikraman Arvind and Pushkar S. Joglekar

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract
In this paper we study the problem of efficiently factorizing polynomials in the free noncommutative ring 𝔽∠{x_1,x_2,…,x_n} of polynomials in noncommuting variables x_1,x_2,…,x_n over the field 𝔽. We obtain the following result: - We give a randomized algorithm that takes as input a noncommutative arithmetic formula of size s computing a noncommutative polynomial f ∈ 𝔽∠{x_1,x_2,…,x_n}, where 𝔽 = 𝔽_q is a finite field, and in time polynomial in s, n and log₂q computes a factorization of f as a product f = f_1f_2 ⋯ f_r, where each f_i is an irreducible polynomial that is output as a noncommutative algebraic branching program. - The algorithm works by first transforming f into a linear matrix L using Higman’s linearization of polynomials. We then factorize the linear matrix L and recover the factorization of f. We use basic elements from Cohn’s theory of free ideals rings combined with Ronyai’s randomized polynomial-time algorithm for computing invariant subspaces of a collection of matrices over finite fields.
Cite as

Vikraman Arvind and Pushkar S. Joglekar. On Efficient Noncommutative Polynomial Factorization via Higman Linearization. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.CCC.2022.12,
  author =	{Arvind, Vikraman and Joglekar, Pushkar S.},
  title =	{{On Efficient Noncommutative Polynomial Factorization via Higman Linearization}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{12:1--12:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.12},
  URN =		{urn:nbn:de:0030-drops-165747},
  doi =		{10.4230/LIPIcs.CCC.2022.12},
  annote =	{Keywords: Noncommutative Polynomials, Arithmetic Circuits, Factorization, Identity testing}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2009.2304
Arithmetic Circuits and the Hadamard Product of Polynomials

Authors: Vikraman Arvind, Pushkar S. Joglekar, and Srikanth Srinivasan

Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)

Abstract
Motivated by the Hadamard product of matrices we define the Hadamard product of multivariate polynomials and study its arithmetic circuit and branching program complexity. We also give applications and connections to polynomial identity testing. Our main results are the following. \begin{itemize} \item[$\bullet$] We show that noncommutative polynomial identity testing for algebraic branching programs over rationals is complete for the logspace counting class $\ceql$, and over fields of characteristic $p$ the problem is in $\ModpL/\Poly$. \item[$\bullet$] We show an exponential lower bound for expressing the Raz-Yehudayoff polynomial as the Hadamard product of two monotone multilinear polynomials. In contrast the Permanent can be expressed as the Hadamard product of two monotone multilinear formulas of quadratic size. \end{itemize}
Cite as

Vikraman Arvind, Pushkar S. Joglekar, and Srikanth Srinivasan. Arithmetic Circuits and the Hadamard Product of Polynomials. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 25-36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.FSTTCS.2009.2304,
  author =	{Arvind, Vikraman and Joglekar, Pushkar S. and Srinivasan, Srikanth},
  title =	{{Arithmetic Circuits and the Hadamard Product of Polynomials}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{25--36},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Kannan, Ravi and Narayan Kumar, K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2304},
  URN =		{urn:nbn:de:0030-drops-23046},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2304},
  annote =	{Keywords: Hadamard product, identity testing, lower bounds, algebraic branching programs}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2008.1738
Some Sieving Algorithms for Lattice Problems

Authors: V. Arvind and Pushkar S. Joglekar

Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)

Abstract
We study the algorithmic complexity of lattice problems based on the sieving technique due to Ajtai, Kumar, and Sivakumar~\cite{aks}. Given a $k$-dimensional subspace $M\subseteq \R^n$ and a full rank integer lattice $\L\subseteq \Q^n$, the \emph{subspace avoiding problem} SAP, defined by Bl\"omer and Naewe \cite{blomer}, is to find a shortest vector in $\L\setminus M$. We first give a $2^{O(n+k \log k)}$ time algorithm to solve \emph{the subspace avoiding problem}. Applying this algorithm we obtain the following results. \begin{enumerate} \item We give a $2^{O(n)}$ time algorithm to compute $i^{th}$ successive minima of a full rank lattice $\L\subset \Q^n$ if $i$ is $O(\frac{n}{\log n})$. \item We give a $2^{O(n)}$ time algorithm to solve a restricted \emph{closest vector problem CVP} where the inputs fulfil a promise about the distance of the input vector from the lattice. \item We also show that unrestricted CVP has a $2^{O(n)}$ exact algorithm if there is a $2^{O(n)}$ time exact algorithm for solving CVP with additional input $v_i\in \L, 1\leq i\leq n$, where $\|v_i\|_p$ is the $i^{th}$ successive minima of $\L$ for each $i$. \end{enumerate} We also give a new approximation algorithm for SAP and the \emph{Convex Body Avoiding problem} which is a generalization of SAP. Several of our algorithms work for \emph{gauge} functions as metric, where the gauge function has a natural restriction and is accessed by an oracle.
Cite as

V. Arvind and Pushkar S. Joglekar. Some Sieving Algorithms for Lattice Problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 25-36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.FSTTCS.2008.1738,
  author =	{Arvind, V. and Joglekar, Pushkar S.},
  title =	{{Some Sieving Algorithms for Lattice Problems}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{25--36},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1738},
  URN =		{urn:nbn:de:0030-drops-17380},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1738},
  annote =	{Keywords: Lattice problems, sieving algorithm, closest vector problem}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact