Theory Seminar, Wednesday Jan 31: Ohad Trabelsi (TTIC) - (Almost) Ruling Out SETH Lower Bounds for All-Pairs Max-Flow

11 views
Skip to first unread message

Arnold Filtser

unread,
Jan 17, 2024, 9:00:39 AMJan 17
to BIU Theory Seminar, oh...@email.com
Hi all,

Next week (24.01.2024) there will be no theory seminar.
The seminar will be back the week after, on Jan 31 with a talk by Ohad Trabelsi. See you there!

Time: 31.01.2024, 12:00
Location:  Building 503 room 226.

Speaker: Ohad Trabelsi (TTIC)
Title: (Almost) Ruling Out SETH Lower Bounds for All-Pairs Max-Flow
Abstract:
The All-Pairs Max-Flow problem has gained significant popularity in the last two decades, and many results are known regarding its fine-grained complexity. Despite this, wide gaps remain in our understanding of the time complexity for several basic variants of the problem, including for directed or undirected graphs, with unit or arbitrary capacities, on the edges or on the nodes.

In this talk, I will describe some recent progress aiming to bridge this gap by providing algorithms, conditional lower bounds, and non-reducibility results.
Based on several joint works with Abhranil Chatterjee, Prerona Chatterjee, Mrinal Kumar and Adrian She.


Best,
Arnold and Talya

Arnold Filtser

unread,
Jan 24, 2024, 3:01:55 AMJan 24
to BIU Theory Seminar, oh...@email.com
Reminder- this week there is no theory seminar.
See you all next week!

On Wed, Jan 17, 2024 at 4:00 PM Arnold Filtser <fil...@cs.biu.ac.il> wrote:
Hi all,

Next week (24.01.2024) there will be no theory seminar.
The seminar will be back the week after, on Jan 31 with a talk by Ohad Trabelsi. See you there!

Time: 31.01.2024, 12:00
Location:  Building 503 room 226.

Speaker: Ohad Trabelsi (TTIC)
Title: (Almost) Ruling Out SETH Lower Bounds for All-Pairs Max-Flow
Abstract:
The All-Pairs Max-Flow problem has gained significant popularity in the last two decades, and many results are known regarding its fine-grained complexity. Despite this, wide gaps remain in our understanding of the time complexity for several basic variants of the problem, including for directed or undirected graphs, with unit or arbitrary capacities, on the edges or on the nodes.

In this talk, I will describe some recent progress aiming to bridge this gap by providing algorithms, conditional lower bounds, and non-reducibility results.


Best,
Arnold and Talya

Arnold Filtser

unread,
Jan 31, 2024, 4:01:07 AMJan 31
to BIU Theory Seminar, oh...@email.com
The seminar starts in one hour!
Reply all
Reply to author
Forward
0 new messages