23 citations · 23 across the 5 of their papers we have counts for
7 papers
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…
Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering
Shyam Narayanan, Sandeep Silwal, Piotr Indyk +1
Random dimensionality reduction is a versatile tool for speeding up algorithms for high-dimensional problems. We study its application to two clustering problems: the facility loca…
Breaking the barrier for 5-coloring and 6-coloring
Or Zamir
The coloring problem (i.e., computing the chromatic number of a graph) can be solved in time, as shown by Björklund, Husfeldt and Koivisto in 2009. For , better a…
Random -out subgraph leaves only inter-component edges
Jacob Holm, Valerie King, Mikkel Thorup +2
Each vertex of an arbitrary simple graph on vertices chooses random incident edges. What is the expected number of edges in the original graph that connect different connec…
Selection from heaps, row-sorted matrices and using soft heaps
Haim Kaplan, László Kozma, Or Zamir +1
We use soft heaps to obtain simpler optimal algorithms for selecting the -th smallest item, and the set of~ smallest items, from a heap-ordered tree, from a collection of sor…