4 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 contras…
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…
A New Impossibility Result for Online Bipartite Matching Problems
Flavio Chierichetti, Mirko Giacchini, Alessandro Panconesi +1
Online Bipartite Matching with random user arrival is a fundamental problem in the online advertisement ecosystem. Over the last 30 years, many algorithms and impossibility results…