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.

Google scholar      DBLP      Publications

Selected Publications:


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

Bridge Girth: A Unifying Notion in Network Design.  with Greg Bodwin and Gary HoppenworthFOCS'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 SaranurakFOCS'22 [arxiv].  Invited to SICOMP Special Issue.

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

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


Service:

ESA'22  ·  STOC'24