Buchumschlag

Deterministic Monotone Min-Plus Product and Convolution

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Jin, Ce, Park, Jaewoo, Saha, Barna, Xu, Yinzhan
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
von: Jin, Ce, et al.
Veröffentlicht: (2024)

Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing
von: Bringmann, Karl, et al.
Veröffentlicht: (2024)

Improved Bounds for Rectangular Monotone Min-Plus Product and Applications
von: Dürr, Anita
Veröffentlicht: (2022)

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

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
von: Nogler, Jakob, et al.
Veröffentlicht: (2024)

Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
von: Black, Hadley, et al.
Veröffentlicht: (2025)

Faster Algorithms for Text-to-Pattern Hamming Distances
von: Chan, Timothy M., et al.
Veröffentlicht: (2023)

New Separations and Reductions for Directed Preservers and Hopsets
von: Hoppenworth, Gary, et al.
Veröffentlicht: (2024)

Approximate Min-Sum Subset Convolution
von: Stoian, Mihail
Veröffentlicht: (2024)

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
von: Saha, Barna, et al.
Veröffentlicht: (2024)

Hardness of Dynamic Tree Edit Distance and Friends
von: Hu, Bingbing, et al.
Veröffentlicht: (2025)

Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
von: Dalirrooyfard, Mina, et al.
Veröffentlicht: (2023)

All-Hops Shortest Paths
von: Williams, Virginia Vassilevska, et al.
Veröffentlicht: (2024)

Memory Reallocation with Polylogarithmic Overhead
von: Jin, Ce
Veröffentlicht: (2026)

0-1 Knapsack in Nearly Quadratic Time
von: Jin, Ce
Veröffentlicht: (2023)

Fairness in Aggregation: Optimal Top-$k$ and Improved Full Ranking
von: Chakraborty, Diptarka, et al.
Veröffentlicht: (2026)

Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time
von: Jin, Wenyu, et al.
Veröffentlicht: (2024)

Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance
von: Das, Debarati, et al.
Veröffentlicht: (2025)

Near-Optimal Property Testers for Pattern Matching
von: Jin, Ce, et al.
Veröffentlicht: (2025)

Approximately Counting Knapsack Solutions in Subquadratic Time
von: Feng, Weiming, et al.
Veröffentlicht: (2024)

A Faster Algorithm for Pigeonhole Equal Sums
von: Jin, Ce, et al.
Veröffentlicht: (2024)

Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time
von: Hua, Kevin, et al.
Veröffentlicht: (2024)

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
von: Anand, Aditya, et al.
Veröffentlicht: (2025)

Language Edit Distance & Scored Parsing: Faster Algorithms & Connection to Fundamental Graph Problems
von: Kociumaka, Tomasz, et al.
Veröffentlicht: (2014)

Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
von: Aamand, Anders, et al.
Veröffentlicht: (2025)

Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold
von: Gu, Yuzhou, et al.
Veröffentlicht: (2025)

Max-Min Diversification with Asymmetric Distances
von: Kumpulainen, Iiro, et al.
Veröffentlicht: (2025)

Clustering with Non-adaptive Subset Queries
von: Black, Hadley, et al.
Veröffentlicht: (2024)

Min-Sum Set Cover on Parallel Machines
von: Szyfelbein, Michał
Veröffentlicht: (2026)

Submodular Ground-Set Pruning: Monotone Tightness and a Non-Monotone Separation
von: Kuhnle, Alan
Veröffentlicht: (2026)

Submodular Max-Min Allocation under Identical Valuations
von: Boehmer, Kimon
Veröffentlicht: (2026)

FPT Approximations for Fair $k$-Min-Sum-Radii
von: Carta, Lena, et al.
Veröffentlicht: (2024)

Parameterized Complexity of MinCSP over the Point Algebra
von: Osipov, George, et al.
Veröffentlicht: (2023)

Online Monotone Metric Embeddings
von: Coester, Christian, et al.
Veröffentlicht: (2026)

Monotone Submodular Multiway Partition
von: Bi, Richard, et al.
Veröffentlicht: (2024)

Streaming Algorithms for Connectivity Augmentation
von: Jin, Ce, et al.
Veröffentlicht: (2024)

Robust Multiagent Collaboration Through Weighted Max-Min T-Joins
von: Alipour, Sharareh
Veröffentlicht: (2026)

More Asymmetry Yields Faster Matrix Multiplication
von: Alman, Josh, et al.
Veröffentlicht: (2024)

Learning Partitions with Optimal Query and Round Complexities
von: Black, Hadley, et al.
Veröffentlicht: (2025)

An Algorithmic Bridge Between Hamming and Levenshtein Distances
von: Goldenberg, Elazar, et al.
Veröffentlicht: (2022)