8 papers · 1 filter
Equivalent Dichotomies for Triangle Detection in Subgraph, Induced, and Colored H-Free Graphs
Amir Abboud, Ron Safier, Nathan Wallheimer
A recent paper by the authors (ITCS'26) initiates the study of the Triangle Detection problem in graphs avoiding a fixed pattern H as a subgraph and proposes a dichotomy hypothesis…
Triangle Detection in H-Free Graphs
Amir Abboud, Ron Safier, Nathan Wallheimer
We initiate the study of combinatorial algorithms for Triangle Detection in -free graphs. The goal is to decide if a graph that forbids a fixed pattern as a subgraph contain…
A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection
Amir Abboud, Shyan Akmal, Nick Fischer
We present the first truly subcubic, combinatorial algorithm for detecting an induced -cycle in a graph. The running time is on -node graphs, thus separating th…
All-Pairs Shortest Paths with Few Weights per Node
Amir Abboud, Nick Fischer, Ce Jin +2
We study the central All-Pairs Shortest Paths (APSP) problem under the restriction that there are at most distinct weights on the outgoing edges from every node. For this…
Recognizing Sumsets is NP-Complete
Amir Abboud, Nick Fischer, Ron Safier +1
Sumsets are central objects in additive combinatorics. In 2007, Granville asked whether one can efficiently recognize whether a given set is a sumset, i.e. whether there is a s…
Worst-Case to Expander-Case Reductions: Derandomized and Generalized
Amir Abboud, Nathan Wallheimer
A recent paper by Abboud and Wallheimer [ITCS 2023] presents self-reductions for various fundamental graph problems, which transform worst-case instances to expanders, thus proving…
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
Amir Abboud, Nick Fischer, Zander Kelley +2
We revisit the fundamental Boolean Matrix Multiplication (BMM) problem. With the invention of algebraic fast matrix multiplication over 50 years ago, it also became known that BMM…
The Time Complexity of Fully Sparse Matrix Multiplication
Amir Abboud, Karl Bringmann, Nick Fischer +1
What is the time complexity of matrix multiplication of sparse integer matrices with nonzeros in the input and nonzeros in the output? This paper provides improv…