Cover Image

Integer multiplication is at least as hard as matrix transposition

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Harvey, David, van der Hoeven, Joris
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Symbolic Computation Primary 68Q17, Secondary 68W30
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Recent Advances in Debordering Methods
by: Dutta, Pranjal, et al.
Published: (2025)

Polynomial-Time Algorithms for Black-Box Distributive Expanded Groups
by: Anokhin, Mikhail
Published: (2025)

A zero-test for D-algebraic transseries
by: Chen, Shaoshi, et al.
Published: (2026)

P not equal to NP
by: Delgado, Daniel Cardona
Published: (2023)

Computing Certificates of Strictly Positive Polynomials in Archimedean Quadratic Modules
by: Shang, Weifeng, et al.
Published: (2025)

A Monadic Calculus with Episodic Flows
by: Henning, Sotirios
Published: (2024)

Sufficient conditions for the surjectivity of radical curve parametrizations
by: Caravantes, Jorce, et al.
Published: (2023)

A Geometric Approach to Cylindrical Algebraic Decomposition
by: Chen, Rizeng
Published: (2023)

Beyond Worst-Case Analysis for Symbolic Computation: Root Isolation Algorithms
by: Ergür, Alperen A., et al.
Published: (2025)

A Kronecker algorithm for locally closed sets over a perfect field
by: Giménez, Nardo, et al.
Published: (2025)

A new method for reducing algebraic programs to polynomial programs
by: Maaz, Muhammad, et al.
Published: (2025)

Exact Volumes of Semi-Algebraic Convex Bodies
by: Ramesh, Lakshmi, et al.
Published: (2026)

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

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
by: Dorochko, Leonid, et al.
Published: (2026)

Misfortunes of a mathematicians' trio using Computer Algebra Systems: Can we trust?
by: Durán, Antonio J., et al.
Published: (2013)

First steps towards Computational Polynomials in Lean
by: Davenport, James Harold
Published: (2024)

Towards Verified Polynomial Factorisation
by: Davenport, James H.
Published: (2024)

On some Exotic Cylindrical Algebraic Decompositions and Cells
by: Michel, Lucas
Published: (2026)

Cylindrical Algebraic Decomposition in Macaulay2
by: Lee, Corin, et al.
Published: (2025)

Provability in BI's Sequent Calculus is Decidable
by: Gheorghiu, Alexander, et al.
Published: (2021)

SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks
by: Marković, Petar, et al.
Published: (2026)

Undefinability of Approximation of 2-to-2 Games
by: Dawar, Anuj, et al.
Published: (2025)

Massively Parallel Modular Methods in Commutative Algebra and Algebraic Geometry
by: Basson, Dirk, et al.
Published: (2024)

CircuitBuilder: From Polynomials to Circuits via Reinforcement Learning
by: Zhang, Weikun K., et al.
Published: (2026)

Jacobi Stability Analysis for Systems of ODEs Using Symbolic Computation
by: Huang, Bo, et al.
Published: (2024)

Recent Developments in Real Quantifier Elimination and Cylindrical Algebraic Decomposition
by: England, Matthew
Published: (2024)

Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem
by: Ilmavirta, Joonas, et al.
Published: (2023)

Friends-and-strangers is PSPACE-complete
by: Yang, Chao, et al.
Published: (2024)

Concatenations of Terms of an Arithmetic Progression
by: Luca, Florian, et al.
Published: (2022)

Certified Real Eigenvalue Location
by: Solmaz, Baran, et al.
Published: (2026)

Effective bounds for polynomial systems defined over the rationals
by: Krick, Teresa
Published: (2025)

Dynamic T-decomposition for classical simulation of quantum circuits
by: Ahmad, Wira Azmoon, et al.
Published: (2024)

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

How to Compute a Moving Sum
by: Maslen, David K., et al.
Published: (2025)

Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
by: Kumar, Mrinal, et al.
Published: (2018)

Revisiting Sampson Approximations for Geometric Estimation Problems
by: Rydell, Felix, et al.
Published: (2024)

The Separation of $NP$ and $PSPACE$
by: Lin, Tianrong
Published: (2021)

Computing moment polytopes -- with a focus on tensors, entanglement and matrix multiplication
by: Berg, Maxim van den, et al.
Published: (2025)

How Does Machine Learning Manage Complexity?
by: Fortnow, Lance
Published: (2026)

Computational Complexity of Determining the Assembly Index
by: Masierak, Piotr
Published: (2026)