Faster Algorithms for Structured Matrix Multiplication via Flip Graph Search

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Khoruzhii, Kirill, Gelß, Patrick, Pokutta, Sebastian
Format:	Preprint
Published:	2025
Subjects:	Symbolic Computation Data Structures and Algorithms 68Q25 F.2.1; F.1.3; G.1.3
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Tensor Decomposition for Non-Clifford Gate Minimization
by: Khoruzhii, Kirill, et al.
Published: (2026)

Shifted Partial Derivative Polynomial Rank and Codimension
by: Edwards, Darren J.
Published: (2025)

$XX^{t}$ Can Be Faster
by: Rybin, Dmitry, et al.
Published: (2025)

I/O complexity and pebble games with partial computations
by: Sobczyk, Aleksandros
Published: (2024)

Complete Decomposition of Symmetric Tensors in Linear Time and Polylogarithmic Precision
by: Koiran, Pascal, et al.
Published: (2022)

Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
by: Spielman, Daniel A., et al.
Published: (2006)

Which graph motif parameters count?
by: Bläser, Markus, et al.
Published: (2025)

Faster Inversion and Other Black Box Matrix Computations Using Efficient Block Projections
by: Eberly, Wayne, et al.
Published: (2007)

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

Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time $O (m^{1.31})$
by: Spielman, Daniel A., et al.
Published: (2003)

Faster Linear Algebra Algorithms with Structured Random Matrices
by: Camaño, Chris, et al.
Published: (2025)

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
by: Rossman, Benjamin
Published: (2024)

Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time
by: Farfan, Angelo, et al.
Published: (2025)

Algorithms for Generating Small Random Samples
by: Cicirello, Vincent A.
Published: (2024)

Required-edge Cycle Cover Problem: an ASP-Completeness Framework for Graph Problems and Puzzles
by: Susukita, Kosuke, et al.
Published: (2026)

Does block size matter in randomized block Krylov low-rank approximation?
by: Chen, Tyler, et al.
Published: (2025)

Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra
by: Bhattacharjee, Rajarshi, et al.
Published: (2023)

Leakage-Resilient Hardness Equivalence to Logspace Derandomization
by: Shalunov, Yakov
Published: (2023)

Line Cover and Related Problems
by: Bentert, Matthias, et al.
Published: (2025)

CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
by: Bodnar, Levente
Published: (2024)

A Simple and Efficient Algorithm for Sorting Signed Permutations by Reversals
by: Swenson, Krister M.
Published: (2024)

On the Average Runtime of an Open Source Binomial Random Variate Generation Algorithm
by: Cicirello, Vincent A.
Published: (2024)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
by: Lela, Marko
Published: (2025)

Certification of the QR factor R, and of lattice basis reducedness
by: Villard, Gilles
Published: (2007)

Meta Theorem for Hardness on FCP-Problem
by: Nagao, Atsuki, et al.
Published: (2025)

Upper and Lower Bounds for the Linear Ordering Principle
by: Hirsch, Edward A., et al.
Published: (2025)

Linear Matroid Intersection is in Catalytic Logspace
by: Agarwala, Aryan, et al.
Published: (2025)

Oracle Separations for RPH
by: Hamm, Thekla, et al.
Published: (2025)

Sign-Rank of $k$-Hamming Distance is Constant
by: Göös, Mika, et al.
Published: (2025)

A Note on Avoid vs MCSP
by: Hirsch, Edward A., et al.
Published: (2025)

Diagonalization Without Relativization A Closer Look at the Baker-Gill-Solovay Theorem
by: Garcia, Baruch
Published: (2026)

Dichotomy for orderings?
by: Kun, Gábor, et al.
Published: (2025)

Space-Time Trade-off in Integer Linear Scaling Rounded to the Nearest Integer through Multiplicative and Additive Decomposition
by: Kim, Kyeong Soo
Published: (2026)

Let them have CAKES: A Cutting-Edge Algorithm for Scalable, Efficient, and Exact Search on Big Data
by: Prior, Morgan E., et al.
Published: (2023)

A 60-Addition, Rank-23 Scheme for Exact 3x3 Matrix Multiplication
by: Stapleton, Joshua
Published: (2025)

Fast Evaluation of Truncated Neumann Series by Low-Product Radix Kernels
by: Sao, Piyush
Published: (2026)

Regular Model Checking for Systems with Effectively Regular Reachability Relation
by: Esparza, Javier, et al.
Published: (2025)

An SoS Entropy Dichotomy via Windowed Hypercontractivity
by: Lela, Marko
Published: (2025)

Failure of the strong feasible disjunction property
by: Krajicek, Jan
Published: (2026)

A Formalization of Co-Transcriptional Splicing as an Operation on Formal Languages
by: Cho, Da-Jung, et al.
Published: (2025)