Ohad Trabelsi

I am a Research Assistant Professor in Computer Science at Toyota Technological Institute. Previously, I was a postdoctoral fellow in Computer Science at The University of Michigan.
I obtained a Ph.D. degree at
Weizmann Institute, where I was fortunate to be advised by Prof. Robert Krauthgamer.

My main research interests are Fine-Grained Complexity and Design of Algorithms, focusing on classic problems such as Max-Flow.

Selected Publications:

Gomory-Hu Tree in Subcubic Time. with Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak . In submission. [arxiv]

Friendly Cut Sparsifiers and Faster Gomory-Hu Trees. with Amir Abboud and Robert Krauthgamer. SODA'22. [arxiv][video]

APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time. with Amir Abboud and Robert Krauthgamer. FOCS'22. [arxiv][video]

Subcubic Algorithms for Gomory-Hu Trees in Unweighted Graphs. with Amir Abboud and Robert Krauthgamer. STOC'21 [arxiv][video]

Cut-Equivalent Trees are Optimal for Min-Cut Queries. with Amir Abboud and Robert Krauthgamer. FOCS'20 [arxiv][video]

New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs. with Amir Abboud and Robert Krauthgamer. SODA'20, ToC'21 [arxiv][video]

The Set Cover Conjecture and Subgraph Isomorphism with a Tree Patern. with Robert Krauthgamer. STACS'19 [arxiv]

Faster Algorithms for All-Pairs Min-Cuts. with Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Przemysław Uznański, Daniel Wolleb-Graf. ICALP'19 [arxiv]

Conditional Lower Bounds for All-Pairs Max-Flow. with Robert Krauthgamer. ICALP'17, TALG'18 [arxiv]