Ron Safier

activity

20222026

collaborators

5 papers

cs.DS2026

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…

cs.DS2025

Triangle Detection in H-Free Graphs

Amir Abboud, Ron Safier, Nathan Wallheimer

We initiate the study of combinatorial algorithms for Triangle Detection in $H$ -free graphs. The goal is to decide if a graph that forbids a fixed pattern $H$ as a subgraph contain…

cs.DS2024

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 $S$ is a sumset, i.e. whether there is a s…

cs.CC2023

Can You Solve Closest String Faster than Exhaustive Search?

Amir Abboud, Nick Fischer, Elazar Goldenberg +2

We study the fundamental problem of finding the best string to represent a given set, in the form of the Closest String problem: Given a set $X \subseteq Σ^{d}$ of $n$ strings, find…

cs.DS2022

Listing 4-Cycles

Amir Abboud, Seri Khoury, Oree Leibowitz +1

In this note we present an algorithm that lists all $4$ -cycles in a graph in time $O ~ (min (n^{2}, m^{4/3}) + t)$ where $t$ is their number. Notably, this separates $4$ -cycle list…