Cover Image

Efficient Polynomial Identity Testing Over Nonassociative Algebras

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Mukhopadhyay, Partha, Ramya, C, Shastri, Pratik
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the Hardness of Order Finding and Equivalence Testing for ROABPs
by: Ramya, C., et al.
Published: (2025)

Lower bounds for planar Arithmetic Circuits
by: Ramya, C., et al.
Published: (2025)

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

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

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

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

Complexity of Nonassociative Lambek Calculus with classical logic
by: Płaczek, Paweł
Published: (2024)

IPS Lower Bounds for Formulas and Sum of ROABPs
by: Chatterjee, Prerona, et al.
Published: (2025)

Maximum Matching and Related Problems in Catalytic Logspace
by: Chakraborty, Srijan, et al.
Published: (2026)

Negations are powerful even in small depth
by: Cavalar, Bruno, et al.
Published: (2025)

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

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

Low-Degree Testing Over Grids
by: Amireddy, Prashanth, et al.
Published: (2023)

Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing
by: Černý, Marek, et al.
Published: (2025)

Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields
by: Dwivedi, Ashish, et al.
Published: (2024)

Solving Polynomial Equations Over Finite Fields
by: Dell, Holger, et al.
Published: (2024)

On Efficient Noncommutative Polynomial Factorization via Higman Linearization
by: Arvind, V., et al.
Published: (2022)

If VNP is hard, then so are equations for it
by: Kumar, Mrinal, et al.
Published: (2020)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
by: Assadi, Sepehr, et al.
Published: (2024)

Polynomial Identity Testing via Evaluation of Rational Functions
by: Hu, Ivan, et al.
Published: (2022)

On the Existence of Algebraic Natural Proofs
by: Chatterjee, Prerona, et al.
Published: (2020)

Testing Isomorphism of Graphs in Polynomial Time
by: Xue, Rui
Published: (2023)

Identity Testing for Radical Expressions
by: Balaji, Nikhil, et al.
Published: (2022)

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

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

Bounds for the Zeros of Polynomials over Quaternion Division Algebra
by: Jan, Ovaisa, et al.
Published: (2026)

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)

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

Computing the Elementary Symmetric Polynomials in Positive Characteristics
by: Orzel, Ian
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)

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

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

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

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

Topics in Non-local Games: Synchronous Algebras, Algebraic Graph Identities, and Quantum NP-hardness Reductions
by: He, Entong
Published: (2024)

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)

Monotone Bounded-Depth Complexity of Homomorphism Polynomials
by: Bhargav, C. S., et al.
Published: (2025)