Document

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

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.

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

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

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.

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

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

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}

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

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

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.

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

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail