Cover Image

New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Abboud, Amir, Fischer, Nick, Kelley, Zander, Lovett, Shachar, Meka, Raghu
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Faster Combinatorial k-Clique Algorithms
by: Abboud, Amir, et al.
Published: (2024)

A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection
by: Abboud, Amir, et al.
Published: (2025)

All-Pairs Shortest Paths with Few Weights per Node
by: Abboud, Amir, et al.
Published: (2025)

On Beating $2^n$ for the Closest Vector Problem
by: Abboud, Amir, et al.
Published: (2025)

Worst-Case to Expander-Case Reductions: Derandomized and Generalized
by: Abboud, Amir, et al.
Published: (2024)

Sparsifying Sums of Positive Semidefinite Matrices
by: Basu, Arpon, et al.
Published: (2025)

Recognizing Sumsets is NP-Complete
by: Abboud, Amir, et al.
Published: (2024)

Triangle Detection in H-Free Graphs
by: Abboud, Amir, et al.
Published: (2025)

Sparse Linear Regression is Easy on Random Supports
by: Chandrasekaran, Gautam, et al.
Published: (2025)

New Algorithm for Combinatorial $n$-folds and Applications
by: Jansen, Klaus, et al.
Published: (2024)

Near-Optimal Directed Low-Diameter Decompositions
by: Bringmann, Karl, et al.
Published: (2025)

Adaptive Flip Graph Algorithm for Matrix Multiplication
by: Arai, Yamato, et al.
Published: (2023)

Beating Bellman's Algorithm for Subset Sum
by: Bringmann, Karl, et al.
Published: (2024)

A Simple Algorithm for Trimmed Multipoint Evaluation
by: Fischer, Nick, et al.
Published: (2025)

Tensor Decompositions and Adiabatic Quantum Computing for Discovering Practical Matrix Multiplication Algorithms
by: Uotila, Valter
Published: (2024)

The communication complexity of distributed estimation
by: Gopalan, Parikshit, et al.
Published: (2025)

Equivalent Dichotomies for Triangle Detection in Subgraph, Induced, and Colored H-Free Graphs
by: Abboud, Amir, et al.
Published: (2026)

An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs using Fast Matrix Multiplication
by: Assadi, Sepehr, et al.
Published: (2025)

Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications
by: Gawrychowski, Paweł, et al.
Published: (2024)

Explicit separations between randomized and deterministic Number-on-Forehead communication
by: Kelley, Zander, et al.
Published: (2023)

Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses
by: Fischer, Nick
Published: (2026)

Sumsets, 3SUM, Subset Sum: Now for Real!
by: Fischer, Nick
Published: (2024)

A Faster Algorithm for Constrained Correlation Clustering
by: Fischer, Nick, et al.
Published: (2025)

Conditionally Tight Algorithms for Maximum k-Coverage and Partial k-Dominating Set via Arity-Reducing Hypercuts
by: Fischer, Nick, et al.
Published: (2026)

New Structures and Algorithms for Length-Constrained Expander Decompositions
by: Haeupler, Bernhard, et al.
Published: (2024)

An Optimal MPC Algorithm for Subunit-Monge Matrix Multiplication, with Applications to LIS
by: Koo, Jaehyun
Published: (2024)

New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching
by: Fischer, Nick, et al.
Published: (2024)

A Unified View of Graph Regularity via Matrix Decompositions
by: Bodwin, Greg, et al.
Published: (2019)

Fine-Grained Computation in 3-Space: Matrix Multiplication and Graph Problems
by: Stout, Quentin F.
Published: (2024)

Matrix Multiplication Reductions
by: Gola, Ashish, et al.
Published: (2024)

Fully Polynomial-time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication
by: Bentert, Matthias, et al.
Published: (2024)

Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition
by: Chuzhoy, Julia, et al.
Published: (2026)

A Practical Linear Time Algorithm for Optimal Tree Decomposition of Halin Graphs
by: Alejandro-Soto, J. A., et al.
Published: (2025)

$\ell_2/\ell_2$ Sparse Recovery via Weighted Hypergraph Peeling
by: Fischer, Nick, et al.
Published: (2025)

Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
by: Fischer, Nick, et al.
Published: (2024)

Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
by: Bernstein, Aaron, et al.
Published: (2025)

Combinatorial Parameterized Algorithms for Chemical Descriptors based on Molecular Graph Sparsity
by: Conrado, Giovanna K., et al.
Published: (2023)

A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
by: Fischer, Nick, et al.
Published: (2024)

From Donkeys to Kings in Tournaments
by: Abboud, Amir, et al.
Published: (2024)

Individual Fairness in Graph Decomposition
by: Munagala, Kamesh, et al.
Published: (2024)