Cover Image

An Optimal MPC Algorithm for Subunit-Monge Matrix Multiplication, with Applications to LIS

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Koo, Jaehyun
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Anarchy in the APSP: Algorithm and Hardness for Incorrect Implementation of Floyd-Warshall
by: Koo, Jaehyun
Published: (2024)

Parallel Batch-Dynamic Algorithms for Spanners, and Extensions
by: Ghaffari, Mohsen, et al.
Published: (2025)

Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees
by: Ghaffari, Mohsen, et al.
Published: (2025)

Dynamic Graph Coloring: Sequential, Parallel, and Distributed
by: Ghaffari, Mohsen, et al.
Published: (2025)

Optimal Approximate Matrix Multiplication over Sliding Window
by: Xian, Haoming, et al.
Published: (2025)

Maximal Palindromes in MPC: Simple and Optimal
by: Pissis, Solon P.
Published: (2025)

New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
by: Abboud, Amir, et al.
Published: (2023)

Optimal Algorithms for Free Order Multiple-Choice Secretary
by: Hajiaghayi, Mohammad Taghi, et al.
Published: (2022)

Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs
by: Łącki, Jakub, et al.
Published: (2025)

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)

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

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

Optimal Approximate Matrix Multiplication over Sliding Windows
by: Yao, Ziqi, et al.
Published: (2025)

Improved Sparse Recovery for Approximate Matrix Multiplication
by: Uffenheimer, Yahel, et al.
Published: (2026)

Matrix Multiplication Verification Using Coding Theory
by: Bennett, Huck, et al.
Published: (2023)

Composition Orderings for Linear Functions and Matrix Multiplication Orderings
by: Kubo, Susumu, et al.
Published: (2024)

Towards Faster Feasible Matrix Multiplication by Trilinear Aggregation
by: Schwartz, Oded, et al.
Published: (2025)

Output-Sparse Matrix Multiplication Using Compressed Sensing
by: Bennett, Huck, et al.
Published: (2025)

On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication
by: Liu, Yang P.
Published: (2024)

Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions
by: Indyk, Piotr, et al.
Published: (2025)

Optimal Extended Formulations from Optimal Dynamic Programming Algorithms
by: Oliveira, Mateus de Oliveira, et al.
Published: (2026)

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

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

An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks
by: Dehghankar, Mohsen, et al.
Published: (2024)

An Optimal Algorithm for Stochastic Vertex Cover
by: Brand, Jan van den, et al.
Published: (2026)

Finding a Shortest $M$-link Path in a Monge Directed Acyclic Graph
by: Wan, Joy Z.
Published: (2024)

Simple and Optimal Sublinear Algorithms for Mean Estimation
by: Bertolotti, Beatrice, et al.
Published: (2024)

An Optimal Algorithm for Sorting Pattern-Avoiding Sequences
by: Opler, Michal
Published: (2024)

Near-Optimal Algorithm for Directed Expander Decompositions
by: Sulser, Aurelio L., et al.
Published: (2024)

Log Diameter Rounds MST Verification and Sensitivity in MPC
by: Coy, Sam, et al.
Published: (2024)

An Optimal Algorithm for Cardinality-Constrained Diameter Partitioning
by: Xu, Chao, et al.
Published: (2026)

Optimal Learning-Augmented Algorithm for Online Bidding
by: Lee, Changyeol, et al.
Published: (2026)

Density-Dependent Graph Orientation and Coloring in Scalable MPC
by: Ghaffari, Mohsen, et al.
Published: (2026)

Round-efficient Fully-scalable MPC algorithms for k-Means
by: Jiang, Shaofeng H. -C., et al.
Published: (2026)

A Note on the Conditional Optimality of Chiba and Nishizeki's Algorithms
by: Kirkpatrick, Yael, et al.
Published: (2024)

An Optimal Sorting Algorithm for Persistent Random Comparison Faults
by: Geissmann, Barbara, et al.
Published: (2025)

A 58-Addition, Rank-23 Scheme for General 3x3 Matrix Multiplication
by: Perminov, A. I.
Published: (2025)

An Algorithm for the Longest Common Subsequence and Substring Problem for Multiple Strings
by: Li, Rao
Published: (2024)