7 papers
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…
Man, these New York Times games are hard! A computational perspective
Alessandro Giovanni Alberti, Flavio Chierichetti, Mirko Giacchini +3
The New York Times (NYT) games have found widespread popularity in recent years and reportedly account for an increasing fraction of the newspaper's readership. In this paper, we b…
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…
Coordinating "7 Billion Humans" is hard
Alessandro Panconesi, Pietro Maria Posta, Mirko Giacchini
In the video game "7 Billion Humans", the player is requested to direct a group of workers to various destinations by writing a program that is executed simultaneously on each work…
Approximating a RUM from Distributions on k-Slates
Flavio Chierichetti, Mirko Giacchini, Ravi Kumar +2
In this work we consider the problem of fitting Random Utility Models (RUMs) to user choices. Given the winner distributions of the subsets of size of a universe, we obtain a p…