Cover Image

Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dudek, Bartłomiej, Fischer, Nick, Gokaj, Geri, Jin, Ce, Künnemann, Marvin, Mao, Xiao, Redžić, Mirza
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Fine-Grained Complexity of Multiple Domination and Dominating Patterns in Sparse Graphs
by: Künnemann, Marvin, et al.
Published: (2024)

Fine-Grained Classification Of Detecting Dominating Patterns
by: Dransfeld, Jonathan, et al.
Published: (2025)

Engineering Dominating Patterns: A Fine-grained Case Study
by: Dransfeld, Jonathan, et al.
Published: (2025)

Completeness Theorems for k-SUM and Geometric Friends: Deciding Fragments of Integer Linear Arithmetic
by: Gokaj, Geri, et al.
Published: (2025)

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

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

Improved Bounds for High-Dimensional Equivalence and Product Testing using Subcube Queries
by: Adar, Tomer, et al.
Published: (2024)

Equivalences between Non-trivial Variants of 3LDT and Conv3LDT
by: Dudek, Bartłomiej, et al.
Published: (2020)

A Strongly Subcubic Combinatorial Algorithm for Triangle Detection with Applications
by: Dumitrescu, Adrian
Published: (2024)

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

The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs
by: Fischer, Nick, et al.
Published: (2025)

A Framework for Parameterized Subexponential-Subcubic-Time Algorithms for Weighted Problems in Planar Graphs
by: Bentert, Matthias, et al.
Published: (2026)

0-1 Knapsack in Nearly Quadratic Time
by: Jin, Ce
Published: (2023)

Memory Reallocation with Polylogarithmic Overhead
by: Jin, Ce
Published: (2026)

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)

Long Arithmetic Progressions in Sumsets and Subset Sums: Constructive Proofs and Efficient Witnesses
by: Chen, Lin, et al.
Published: (2025)

Distributed Model Checking on Graphs of Bounded Treedepth
by: Fomin, Fedor V., et al.
Published: (2024)

Near-Optimal Property Testers for Pattern Matching
by: Jin, Ce, et al.
Published: (2025)

Approximately Counting Knapsack Solutions in Subquadratic Time
by: Feng, Weiming, et al.
Published: (2024)

Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
by: Jin, Ce, et al.
Published: (2024)

A Faster Algorithm for Pigeonhole Equal Sums
by: Jin, Ce, et al.
Published: (2024)

Hardness of Median and Center in the Ulam Metric
by: Fischer, Nick, 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)

Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning
by: Chakrabarty, Deeparnab, et al.
Published: (2025)

The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds
by: Bringmann, Karl, et al.
Published: (2023)

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

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

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

Computing $L_\infty$ Hausdorff Distances Under Translations: The Interplay of Dimensionality, Symmetry and Discreteness
by: Angrick, Sebastian, et al.
Published: (2026)

Approximating Pareto Sum via Bounded Monotone Min-Plus Convolution
by: Gokaj, Geri, et al.
Published: (2026)

Deterministic Monotone Min-Plus Product and Convolution
by: Jin, Ce, et al.
Published: (2026)

Streaming Algorithms for Connectivity Augmentation
by: Jin, Ce, et al.
Published: (2024)

$(1-ε)$-Approximation of Knapsack in Nearly Quadratic Time
by: Mao, Xiao
Published: (2023)

Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
by: Mao, Xiao
Published: (2023)

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

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

Node-Weighted Triangles: Faster and Simpler
by: Akmal, Shyan, et al.
Published: (2026)