Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > FACTORIZATION:
Reports tagged with Factorization:
TR10-036 | 8th March 2010
Amir Shpilka, Ilya Volkovich

#### On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors

We say that a polynomial $f(x_1,\ldots,x_n)$ is {\em indecomposable} if it cannot be written as a product of two polynomials that are defined over disjoint sets of variables. The {\em polynomial decomposition} problem is defined to be the task of finding the indecomposable factors of a given polynomial. Note that ... more >>>

TR14-018 | 13th February 2014
Arnab Bhattacharyya

#### Polynomial decompositions in polynomial time

Fix a prime $p$. Given a positive integer $k$, a vector of positive integers ${\bf \Delta} = (\Delta_1, \Delta_2, \dots, \Delta_k)$ and a function $\Gamma: \mathbb{F}_p^k \to \F_p$, we say that a function $P: \mathbb{F}_p^n \to \mathbb{F}_p$ is $(k,{\bf \Delta},\Gamma)$-structured if there exist polynomials $P_1, P_2, \dots, P_k:\mathbb{F}_p^n \to \mathbb{F}_p$ ... more >>>

TR22-042 | 31st March 2022
Vikraman Arvind, Pushkar Joglekar

#### 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.
\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 >>>

TR23-139 | 18th September 2023
Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi

#### Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits

For every constant $d$, we design a subexponential time deterministic algorithm that takes as input a multivariate polynomial $f$ given as a constant depth algebraic circuit over the field of rational numbers, and outputs all irreducible factors of $f$ of degree at most $d$ together with their respective multiplicities. Moreover, ... more >>>

ISSN 1433-8092 | Imprint