Lior Kamma

activity

20132024

most citedFully Understanding the Hashing Trick

14 citations · 40 across the 12 of their papers we have counts for

collaborators

Showing 2015Show all

2 papers · 1 filter

cs.DS2015

Tight Bounds for Gomory-Hu-like Cut Counting

Rajesh Chitnis, Lior Kamma, Robert Krauthgamer

By a classical result of Gomory and Hu (1961), in every edge-weighted graph $G = (V, E, w)$ , the minimum $s t$ -cut values, when ranging over all $s, t \in V$ , take at most $∣ V ∣ - 1$ distinc…

cs.DS2015

Metric Decompositions of Path-Separable Graphs

Lior Kamma, Robert Krauthgamer

A prominent tool in many problems involving metric spaces is a notion of randomized low-diameter decomposition. Loosely speaking, $β$ -decomposition refers to a probability distribu…