Cover Image

On Efficient Noncommutative Polynomial Factorization via Higman Linearization

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Arvind, V., Joglekar, Pushkar S.
Format:	Preprint
Published:	2022
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results
by: Arvind, Vikraman, et al.
Published: (2024)

Trading Determinism for Noncommutativity in Edmonds' Problem
by: Arvind, V., et al.
Published: (2024)

Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
by: Arvind, V., et al.
Published: (2023)

Some properties of Higman-Thompson monoids and digital circuits
by: Birget, J. C.
Published: (2024)

Derandomizing Multivariate Polynomial Factoring for Low Degree Factors
by: Dutta, Pranjal, et al.
Published: (2024)

On Factorization of Sparse Polynomials of Bounded Individual Degree
by: Chuyoon, Aminadav, et al.
Published: (2026)

A Quadratic Lower Bound for Noncommutative Circuits
by: Shastri, Pratik
Published: (2026)

Almost Polynomial Factor Inapproximability for Parameterized k-Clique
by: S., Karthik C., et al.
Published: (2021)

Efficient Polynomial Identity Testing Over Nonassociative Algebras
by: Mukhopadhyay, Partha, et al.
Published: (2025)

Derandomizing Isolation In Catalytic Logspace
by: Arvind, V., et al.
Published: (2025)

Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming
by: Gibor, Daniel
Published: (2025)

A New Reduction Method from Multivariate Polynomials to Univariate Polynomials
by: Wang, Cancan, et al.
Published: (2024)

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
by: Sajith, Thejas Radhika
Published: (2025)

Simple Norm Bounds for Polynomial Random Matrices via Decoupling
by: Tulsiani, Madhur, et al.
Published: (2024)

On a Hierarchy of Spectral Invariants for Graphs
by: Arvind, V., et al.
Published: (2023)

On Matrix Multiplication and Polynomial Identity Testing
by: Andrews, Robert
Published: (2022)

Lifting with Inner Functions of Polynomial Discrepancy
by: Manor, Yahel, et al.
Published: (2024)

Symmetric Algebraic Circuits and Homomorphism Polynomials
by: Dawar, Anuj, et al.
Published: (2025)

On Boolean PCSPs with Polynomial Threshold Polymorphisms
by: Michno, Katzper
Published: (2025)

Attacking the Polynomials in the Maze of Finite Fields problem
by: Barbero, Àngela, et al.
Published: (2026)

One-Way Functions and Polynomial Time Dimension
by: Nandakumar, Satyadev, et al.
Published: (2024)

Computing the Elementary Symmetric Polynomials in Positive Characteristics
by: Orzel, Ian
Published: (2025)

Extractors for Polynomial Sources over $\mathbb{F}_2$
by: Chattopadhyay, Eshan, et al.
Published: (2023)

Polynomial-Time PIT from (Almost) Necessary Assumptions
by: Andrews, Robert, et al.
Published: (2025)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
by: Jiang, Cheng, et al.
Published: (2026)

Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
by: Komarath, Balagopal, et al.
Published: (2025)

Polynomial and analytic methods for classifying complexity of planar graph homomorphisms
by: Cai, Jin-Yi, et al.
Published: (2024)

The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth
by: Kahanamoku-Meyer, Gregory D., et al.
Published: (2024)

Low-Degree Polynomials Are Good Extractors
by: Alrabiah, Omar, et al.
Published: (2024)

Positive Univariate Polynomials: SOS certificates, algorithms, bit complexity, and T-systems
by: Bender, Matías, et al.
Published: (2025)

Polynomial Lower Bounds for Arithmetic Circuits over Non-Commutative Rings
by: Raz, Ran
Published: (2026)

A Near-Optimal Polynomial Distance Lemma Over Boolean Slices
by: Amireddy, Prashanth, et al.
Published: (2025)

A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions
by: Yao, Penghui, et al.
Published: (2025)

Information-Based Complexity vs Computational Complexity in Phaseless Polynomial Interpolation
by: Przybyłek, Michał R., et al.
Published: (2026)

A Critique of Quigley's "A Polynomial Time Algorithm for 3SAT"
by: DeJesse, Nicholas, et al.
Published: (2025)

A Critique of Du's "A Polynomial-Time Algorithm for 3-SAT
by: He, Yumeng, et al.
Published: (2024)

Optimal Polynomial-Time Estimators: A Bayesian Notion of Approximation Algorithm
by: Kosoy, Vanessa, et al.
Published: (2016)

Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy
by: Chia, Nai-Hui, et al.
Published: (2024)

Polynomial Identity Testing and Reconstruction for Depth-4 Powering Circuits of High Degree
by: Shpilka, Amir, et al.
Published: (2026)

A Critique of Chen's "The 2-MAXSAT Problem Can Be Solved in Polynomial Time"
by: Le, Tran Duy Anh, et al.
Published: (2024)