14 citations · 40 across the 12 of their papers we have counts for
8 papers · 1 filter
A New Approach for Approximating Directed Rooted Networks
Sarel Cohen, Lior Kamma, Aikaterini Niklanovits
We consider the k-outconnected directed Steiner tree problem (k-DST). Given a directed edge-weighted graph , where , and an integer , the goal i…
Lower Bounds for Multiplication via Network Coding
Peyman Afshani, Casper Benjamin Freksen, Lior Kamma +1
Multiplication is one of the most fundamental computational problems, yet its true complexity remains elusive. The best known upper bound, by Fürer, shows that two -bit numbers…
Batch Sparse Recovery, or How to Leverage the Average Sparsity
Alexandr Andoni, Lior Kamma, Robert Krauthgamer +1
We introduce a \emph{batch} version of sparse recovery, where the goal is to report a sequence of vectors that estimate unknown signals $A_1,\ld…
Nearly Optimal Time Bounds for kPath in Hypergraphs
Lior Kamma, Ohad Trabelsi
We give almost tight conditional lower bounds on the running time of the kHyperPath problem. Given an -uniform hypergraph for some integer , kHyperPath seeks a tight path of…
Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication
Diptarka Chakraborty, Lior Kamma, Kasper Green Larsen
The conjectured hardness of Boolean matrix-vector multiplication has been used with great success to prove conditional lower bounds for numerous important data structure problems,…
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 , the minimum -cut values, when ranging over all , take at most distinc…
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…
Cutting corners cheaply, or how to remove Steiner points
Lior Kamma, Robert Krauthgamer, Huy L. Nguyen
Our main result is that the Steiner Point Removal (SPR) problem can always be solved with polylogarithmic distortion, which answers in the affirmative a question posed by Chan, Xia…