
Randomized Dimensionality Reduction for Facility Location and SingleLinkage Clustering
Random dimensionality reduction is a versatile tool for speeding up algo...
read it

Breaking the 2^n barrier for 5coloring and 6coloring
The coloring problem (i.e., computing the chromatic number of a graph) c...
read it

Random kout subgraph leaves only O(n/k) intercomponent edges
Each vertex of an arbitrary simple graph on n vertices chooses k random ...
read it

Selection from heaps, rowsorted matrices and X+Y using soft heaps
We use soft heaps to obtain simpler optimal algorithms for selecting the...
read it
Or Zamir
is this you? claim profile