Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > POLYNOMIAL FACTORIZATION:
Reports tagged with polynomial factorization:
TR14-001 | 4th January 2014
Swastik Kopparty, Shubhangi Saraf, Amir Shpilka

Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization

In this paper we show that the problem of deterministically factoring multivariate polynomials reduces to the problem of deterministic polynomial identity testing. Specifically, we show that given an arithmetic circuit (either explicitly or via black-box access) that computes a polynomial $f(X_1,\ldots,X_n)$, the task of computing arithmetic circuits for the factors ... more >>>


TR22-022 | 18th February 2022
Vikraman Arvind, Pushkar Joglekar

On Efficient Noncommutative Polynomial Factorization via Higman Linearization

Revisions: 4

In this paper we study the problem of efficiently factorizing polynomials in the free noncommutative ring F of polynomials in noncommuting variables x_1,x_2,…,x_n over the field F. We obtain the following result:

Given a noncommutative arithmetic formula of size s computing a noncommutative polynomial f in F as input, where ... more >>>


TR24-043 | 4th March 2024
Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Ben Lee Volk

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits

We design a deterministic subexponential time algorithm that takes as input a multivariate polynomial $f$ computed by a constant-depth circuit over rational numbers, and outputs a list $L$ of circuits (of unbounded depth and possibly with division gates) that contains all irreducible factors of $f$ computable by constant-depth circuits. This ... more >>>


TR24-197 | 29th November 2024
Pranjal Dutta, Amit Sinhababu, Thomas Thierauf

Derandomizing Multivariate Polynomial Factoring for Low Degree Factors

For a polynomial $f$ from a class $\mathcal{C}$ of polynomials, we show that the problem to compute all the constant degree irreducible factors of $f$ reduces in polynomial time to polynomial identity tests (PIT) for class $\mathcal{C}$ and divisibility tests of $f$ by constant degree polynomials. We apply the result ... more >>>


TR25-044 | 10th April 2025
Somnath Bhattacharjee, Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf

Deterministic factorization of constant-depth algebraic circuits in subexponential time

Revisions: 1

While efficient randomized algorithms for factorization of polynomials given by algebraic circuits have been known for decades, obtaining an even slightly non-trivial deterministic algorithm for this problem has remained an open question of great interest. This is true even when the input algebraic circuit has additional structure, for instance, when ... more >>>


TR25-083 | 24th June 2025
C.S. Bhargav, Prateek Dwivedi, Nitin Saxena

A primer on the closure of algebraic complexity classes under factoring

Polynomial factorization is a fundamental problem in computational algebra. Over the past half century, a variety of algorithmic techniques have been developed to tackle different variants of this problem. In parallel, algebraic complexity theory classifies polynomials into complexity classes based on their perceived `hardness'. This raises a natural question: Do ... more >>>




ISSN 1433-8092 | Imprint