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 Hoppenworth. FOCS'23 (to appear) [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.
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'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]
Relaxed voronoi: A simple framework for terminal-clustering problems. with Robert Krauthgamer and Arnold Filtser. SOSA'19 [arxiv]
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]
Nearly Optimal Bounds for k-Path in Hypergraphs. with Lior Kamma. Manuscript [arxiv]
Bounded-hop communication networks. with Lilach Chaitman-Yerushalmi and Paz Carmi. Algorithmica'18 [journal]
Conditional Lower Bounds for All-Pairs Max-Flow. with Robert Krauthgamer. ICALP'17, TALG'18 [arxiv]
On the Bounded-Hop Range Assignment Problem. with Lilach Chaitman-Yerushalmi and Paz Carmi. WADS'15 [conference]