14 citations · 20 across the 13 of their papers we have counts for
3 papers · 1 filter
Sketching Intersection Profiles: A Simple Proof and Three Applications
Flavio Chierichetti, Mirko Giacchini, Ravi Kumar +3
In this work we settle the complexity of three sketching problems. (i) We show that sketching vertex neighborhood sizes in graphs requires bits, standing in sharp contrast…
On the LSH Distortion of Ulam and Cayley Similarities
Flavio Chierichetti, Mirko Giacchini, Ravi Kumar +1
Locality-sensitive hashing (LSH) has found widespread use as a fundamental primitive, particularly to accelerate nearest neighbor search. An LSH scheme for a similarity function $S…
Learning Multinomial Logits in time
Flavio Chierichetti, Mirko Giacchini, Ravi Kumar +4
A Multinomial Logit (MNL) model is composed of a finite universe of items , each assigned a positive weight. A query specifies an admissible subset -- called a sl…