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.

Publications: List Google scholar DBLP

Selected Publications:

Breaking the O(mn)-Time Barrier for Vertex-Weighted Global Minimum Cut. with Julia Chuzhoy. STOC'25 (accepted)

(Almost) Ruling Out SETH Lower Bounds for All-Pairs Max-Flow. SODA'25 [arxiv]

Bridge Girth: A Unifying Notion in Network Design. with Greg Bodwin and Gary Hoppenworth. FOCS'23 [arxiv][video]

Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time. with Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak. FOCS'22 [arxiv]. Invited to SICOMP Special Issue.

APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time. with Amir Abboud and Robert Krauthgamer. FOCS'21 [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]

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

PC Member:

ESA'22 · STOC'24

Page updated

Google Sites

Report abuse