14 citations · 40 across the 12 of their papers we have counts for
13 papers
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…
Compression Implies Generalization
Allan Grønlund, Mikael Høgsgaard, Lior Kamma +1
Explaining the surprising generalization performance of deep neural networks is an active and important line of research in theoretical machine learning. Influential work by Arora…
Margins are Insufficient for Explaining Gradient Boosting
Allan Grønlund, Lior Kamma, Kasper Green Larsen
Boosting is one of the most successful ideas in machine learning, achieving great practical performance with little fine-tuning. The success of boosted classifiers is most often at…
Near-Tight Margin-Based Generalization Bounds for Support Vector Machines
Allan Grønlund, Lior Kamma, Kasper Green Larsen
Support Vector Machines (SVMs) are among the most fundamental tools for binary classification. In its simplest formulation, an SVM produces a hyperplane separating two classes of d…
Margin-Based Generalization Lower Bounds for Boosted Classifiers
Allan Grønlund, Lior Kamma, Kasper Green Larsen +2
Boosting is one of the most successful ideas in machine learning. The most well-accepted explanations for the low generalization error of boosting algorithms such as AdaBoost stem…
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…
Fully Understanding the Hashing Trick
Casper Benjamin Freksen, Lior Kamma, Kasper Green Larsen
Feature hashing, also known as {\em the hashing trick}, introduced by Weinberger et al. (2009), is one of the key techniques used in scaling-up machine learning algorithms. Loosely…
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…