Theory Seminar, Wednesday May 20: Ariel Korin (BIU) - New Hopset Lower Bounds for Exact Distances

[Arnold Filtser]

Hi all,

This week (Wednesday May 13) there is no theory seminar.

The next seminar will take place next week (Wednesday May 20, at 12pm). The talk will be by Ariel Korin who will tell us about hop-sets lower bounds.

Location: Building 503 room 226.

Looking forward to seeing you all there,
Arnold
https://theory.cs.biu.ac.il/


Speaker: Ariel Korin (BIU)
Title: New Hopset Lower Bounds for Exact Distances
Abstract: In the shortcut set problem, given a directed graph $G$ with $n$ vertices and $m$ edges, the goal is to add a (small) set $H$ of directed edges to $G$ that reduces the diameter of $G$, while preserving its transitive closure.

In the similar hopset problem, the goal of $H$ is to reduce the maximum number of edges in a shortest path in $G$ (also known as the hopbound), while not changing the distance between any pair of vertices in $G$.

V. Williams, Xu and Xu [SODA’ 24] showed that there exist directed graphs such that no shortcut set of size $O(n)$ can reduce the diameter to below $\Omega(n^{1/4})$. Hoppenworth, Xu and Xu [SODA’ 25] showed that there exist unweighted graphs such that no exact distance hopset of size $O(m)$ can reduce the hopbound to below $\Omega(n^{2/7})$.

In my talk I will present a base case of a generalization of the construction by Hoppenworth, Xu and Xu [SODA’ 25].
This base case construction implies that there exist graphs with constant edge weights such that no shortcut set of size $O(n)$ can reduce the hopbound to below $\Omega(n^{1/3})$.

[Arnold Filtser]

Reminder: this Wed Ariel will speak about hopset lower bounds.

See you there.

Have a great week,

Arnold

[Arnold Filtser]

The talk starts in one hour!