Cover Image

Modular composition & polynomial GCD in the border of small, shallow circuits

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Andrews, Robert, Kumar, Mrinal, Rai, Shanthanu S.
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Symbolic Computation
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Constant-depth circuits for polynomial GCD over any characteristic
by: Bhattacharjee, Somnath, et al.
Published: (2025)

Constant-Depth Arithmetic Circuits for Linear Algebra Problems
by: Andrews, Robert, et al.
Published: (2024)

Hilbert's Nullstellensatz is in the Counting Hierarchy
by: Andrews, Robert, et al.
Published: (2026)

Fast polynomial computations with space constraints
by: Grenet, Bruno
Published: (2025)

Fast interpolation and multiplication of unbalanced polynomials
by: Giorgi, Pascal, et al.
Published: (2024)

A quasi-optimal lower bound for skew polynomial multiplication
by: Chen, Qiyuan, et al.
Published: (2024)

Primes via Zeros: Interactive Proofs for Testing Primality of Natural Classes of Ideals
by: Garg, Abhibhav, et al.
Published: (2025)

Matrices with displacement structure: a deterministic approach for linear systems and nullspace bases
by: Khichane, Sara, et al.
Published: (2026)

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

Relating the Computational and Logical Difficulty of Solving ODEs: From Polynomial to Discontinuous Right-Hand Sides
by: Bournez, Olivier, et al.
Published: (2026)

Computing Polynomial Representation in Subrings of Multivariate Polynomial Rings
by: Vu, Thi Xuan
Published: (2025)

A New Bound on Cofactors of Sparse Polynomials
by: Nahshon, Ido, et al.
Published: (2023)

On the complexity of Chow and Hurwitz forms
by: Doğan, Mahmut Levent, et al.
Published: (2022)

Quantifier Elimination Meets Treewidth
by: Wu, Hao, et al.
Published: (2026)

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

Runtime Repeated Recursion Unfolding in CHR: A Just-In-Time Online Program Optimization Strategy That Can Achieve Super-Linear Speedup
by: Fruehwirth, Thom
Published: (2023)

Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields
by: Rai, Shanthanu S
Published: (2024)

Closure under factorization from a result of Furstenberg
by: Bhattacharjee, Somnath, et al.
Published: (2025)

A Complexity Map of Probabilistic Reasoning for Neurosymbolic Classification Techniques
by: Ledaguenel, Arthur, et al.
Published: (2024)

Trinomials and Deterministic Complexity Limits for Real Solving
by: Boniface, Emma, et al.
Published: (2022)

A Faster Solution to Smale's 17th Problem I: Real Binomial Systems
by: Paouris, Grigoris, et al.
Published: (2019)

Complexity Classification of Complex-Weighted Counting Acyclic Constraint Satisfaction Problems
by: Yamakami, Tomoyuki
Published: (2024)

The Scaling Properties of Implicit Deductive Reasoning in Transformers
by: Vompa, Enrico, et al.
Published: (2026)

On the gradient of the coefficient of the characteristic polynomial
by: Ikenmeyer, Christian
Published: (2025)

Extrapolating Solution Paths of Polynomial Homotopies towards Singularities with PHCpack and phcpy
by: Verschelde, Jan, et al.
Published: (2024)

Deciding One to One property of Boolean maps: Condition and algorithm in terms of implicants
by: Sule, Virendra
Published: (2023)

Computing greatest common divisor of several parametric univariate polynomials via generalized subresultant polynomials
by: Hong, Hoon, et al.
Published: (2023)

Probably faster multiplication of sparse polynomials
by: van der Hoeven, Joris
Published: (2025)

Solving parametric polynomial systems using Generic Rational Univariate Representation
by: Corniquel, Florent
Published: (2026)

Computing submatrices of the Hermite normal form of a structured polynomial matrix
by: Berthomieu, Jérémy, et al.
Published: (2026)

Algorithmic reduction of polynomially nonlinear PDE systems to parametric ODE systems
by: Deng, Siyuan, et al.
Published: (2024)

Integer multiplication is at least as hard as matrix transposition
by: Harvey, David, et al.
Published: (2025)

Modular Stochastic Rewritable Petri Nets
by: Capra, Lorenzo
Published: (2025)

Efficient Performance Analysis of Modular Rewritable Petri Nets
by: Capra, Lorenzo, et al.
Published: (2024)

Faster modular composition using two relation matrices
by: Neiger, Vincent, et al.
Published: (2026)

Factoring sparse polynomials fast
by: Demin, Alexander, et al.
Published: (2023)

Local Hamiltonian decomposition and classical simulation of parametrized quantum circuits
by: Adhikari, Bibhas, et al.
Published: (2024)

Fast interpolation of sparse multivariate polynomials
by: van der Hoeven, Joris, et al.
Published: (2023)

Modular Algorithms For Computing Gröbner Bases in Free Algebras
by: Hofstadler, Clemens, et al.
Published: (2025)

Certificates for nonnegativity of multivariate integer polynomials under perturbations
by: Bender, Matías R, et al.
Published: (2025)