23 citations · 53 across the 24 of their papers we have counts for
4 papers · 1 filter
Algorithmic Applications of Hypergraph and Partition Containers
Or Zamir
We present a general method to convert algorithms into faster algorithms for almost-regular input instances. Informally, an almost-regular input is an input in which the maximum de…
The wrong direction of Jensen's inequality is algorithmically right
Or Zamir
Let be an algorithm with expected running time , conditioned on the value of some random variable . We construct an algorithm with expected run…
Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond
Amir Abboud, Karl Bringmann, Seri Khoury +1
We present a new technique for efficiently removing almost all short cycles in a graph without unintentionally removing its triangles. Consequently, triangle finding problems do no…
Planting Undetectable Backdoors in Machine Learning Models
Shafi Goldwasser, Michael P. Kim, Vinod Vaikuntanathan +1
Given the computational cost and technical expertise required to train machine learning models, users may delegate the task of learning to a service provider. We show how a malicio…