Flavio Chierichetti

TCS Journal 2025 Journal Article

Instance-optimal information-based voting

• Flavio Chierichetti

The classical Condorcet Jury Theorem considers a voting scenario in which there exists a candidate whose election would be ideal for each voter; each voter, though, has only a limited understanding of the world and is thus unable to determine exactly who this candidate is. The main question in this scenario is whether the voters, acting individually, can cast their ballots so that the unknown optimal candidate wins the election, and the welfare of the group of voters is maximized. In this setting, each candidate is represented by a known probability distribution over signals about the world that the voters can perceive, that is, over bits. One of these candidates is chosen (secretively, by an adversary) to be the ideal candidate. Afterwards, each voter samples this unknown candidate's distribution once and casts a ballot with the hope that the unknown ideal candidate wins the election. In this paper, we consider the famous Condorcet voting system, as well as some of its variants. First, we give a positive answer to an open question of Chierichetti and Kleinberg [8], and show that, with Condorcet voting, there exists a uniform voting strategy that makes the group of voters succeed with probability 1 − δ provided that Θ ( ϵ tv − 2 ⋅ ln ⁡ δ − 1 ) voters take part in the election — here, ϵ tv is the minimum total variation distance between the distributions of two candidates. We also give a uniform voting strategy for the Copeland voting system (a variant of Condorcet) that makes the group succeed with probability 1 − δ with Θ ( ϵ H − 2 ⋅ ln ⁡ δ − 1 ) voters, where ϵ H is the minimum Hellinger distance between the distributions. Our uniform Copeland strategy, then, is an instance-optimal hypothesis testing algorithm: constants aside, the strategy is as efficient as the optimal omniscient algorithm which determines the unknown candidate after having directly observed each of the signals perceived by the voters. Then, we “derandomize” our uniform Copeland strategy, and obtain a Condorcet strategy that achieves instance-optimality at the cost of losing uniformity; finally, we prove that this loss of uniformity is necessary: no uniform Condorcet strategy can achieve instance-optimality, in general. Thus, the right voting strategies let these classical combinatorial voting systems attain the same efficiency of centralized, optimal, hypothesis testers.

NeurIPS Conference 2024 Conference Paper

Tight Bounds for Learning RUMs from Small Slates

• Flavio Chierichetti
• Mirko Giacchini
• Ravi Kumar
• Alessandro Panconesi
• Andrew Tomkins

A Random Utility Model (RUM) is a classical model of user behavior defined by a distribution over $\mathbb{R}^n$. A user, presented with a subset of $\\{1, \ldots, n\\}$, will select the item of the subset with the highest utility, according to a utility vector drawn from the specified distribution. In practical settings, the subset is often of small size, as in the ``ten blue links'' of web search. In this paper, we consider a learning setting with complete information on user choices from subsets of size at most $k$. We show that $k=\Theta(\sqrt{n})$ is both necessary and sufficient to predict the distribution of all user choices with an arbitrarily small, constant error. Based on the upper bound, we obtain new algorithms for approximate RUM learning and variations thereof. Furthermore, we employ our lower bound for approximate RUM learning to derive lower bounds to fractional extensions of the well-studied $k$-deck and trace reconstruction problems.

TCS Journal 2022 Journal Article

On additive approximate submodularity

• Flavio Chierichetti
• Anirban Dasgupta
• Ravi Kumar

A real-valued set function is (additively) approximately submodular if it satisfies the submodularity conditions with an additive error. Approximate submodularity arises in many settings, especially in machine learning, where the function evaluation might not be exact. In this paper we study how close such approximately submodular functions are to truly submodular functions. We show that an approximately submodular function defined on a ground set of n elements is O ( n 2 ) pointwise-close to a submodular function. This result also provides an algorithmic tool that can be used to adapt existing submodular optimization algorithms to approximately submodular functions. To complement, we show an Ω ( n ) lower bound on the distance to submodularity. These results stand in contrast to the case of approximate modularity, where the distance to modularity is a constant, and approximate convexity, where the distance to convexity is logarithmic.

ICML Conference 2022 Conference Paper

RUMs from Head-to-Head Contests

• Matteo Almanza
• Flavio Chierichetti
• Ravi Kumar 0001
• Alessandro Panconesi
• Andrew Tomkins

Random utility models (RUMs) encode the likelihood that a particular item will be selected from a slate of competing items. RUMs are well-studied objects in both discrete choice theory and, more recently, in the machine learning community, as they encode a fairly broad notion of rational user behavior. In this paper, we focus on slates of size two representing head-to-head contests. Given a tournament matrix $M$ such that $M_{i, j}$ is the probability that item $j$ will be selected from $\{i, j\}$, we consider the problem of finding the RUM that most closely reproduces $M$. For this problem we obtain a polynomial-time algorithm returning a RUM that approximately minimizes the average error over the pairs. Our experiments show that RUMs can perfectly represent many of the tournament matrices that have been considered in the literature; in fact, the maximum average error induced by RUMs on the matrices we considered is negligible ($\approx 0. 001$). We also show that RUMs are competitive, on prediction tasks, with previous approaches.

ICML Conference 2021 Conference Paper

Light RUMs

• Flavio Chierichetti
• Ravi Kumar 0001
• Andrew Tomkins

A Random Utility Model (RUM) is a distribution on permutations over a universe of items. For each subset of the universe, a RUM induces a natural distribution of the winner in the subset: choose a permutation according to the RUM distribution and pick the maximum item in the subset according to the chosen permutation. RUMs are widely used in the theory of discrete choice. In this paper we consider the question of the (lossy) compressibility of RUMs on a universe of size $n$, i. e. , the minimum number of bits required to approximate the winning probabilities of each slate. Our main result is that RUMs can be approximated using $\tilde{O}(n^2)$ bits, an exponential improvement over the standard representation; furthermore, we show that this bound is optimal. En route, we sharpen the classical existential result of McFadden and Train (2000) by showing that the minimum size of a mixture of multinomial logits required to can approximate a general RUM is $\tilde{\Theta}(n)$.

NeurIPS Conference 2021 Conference Paper

Online Facility Location with Multiple Advice

• Matteo Almanza
• Flavio Chierichetti
• Silvio Lattanzi
• Alessandro Panconesi
• Giuseppe Re

Clustering is a central topic in unsupervised learning and its online formulation has received a lot of attention in recent years. In this paper, we study the classic facility location problem in the presence of multiple machine-learned advice. We design an algorithm with provable performance guarantees such that, if the advice is good, it outperforms the best-known online algorithms for the problem, and if it is bad it still matches their performance. We complement our theoretical analysis with an in-depth study of the performance of our algorithm, showing its effectiveness on synthetic and real-world data sets.

NeurIPS Conference 2018 Conference Paper

A Reduction for Efficient LDA Topic Reconstruction

• Matteo Almanza
• Flavio Chierichetti
• Alessandro Panconesi
• Andrea Vattani

We present a novel approach for LDA (Latent Dirichlet Allocation) topic reconstruction. The main technical idea is to show that the distribution over the documents generated by LDA can be transformed into a distribution for a much simpler generative model in which documents are generated from {\em the same set of topics} but have a much simpler structure: documents are single topic and topics are chosen uniformly at random. Furthermore, this reduction is approximation preserving, in the sense that approximate distributions-- the only ones we can hope to compute in practice-- are mapped into approximate distribution in the simplified world. This opens up the possibility of efficiently reconstructing LDA topics in a roundabout way. Compute an approximate document distribution from the given corpus, transform it into an approximate distribution for the single-topic world, and run a reconstruction algorithm in the uniform, single topic world-- a much simpler task than direct LDA reconstruction. Indeed, we show the viability of the approach by giving very simple algorithms for a generalization of two notable cases that have been studied in the literature, $p$-separability and Gibbs sampling for matrix-like topics.

SODA Conference 2018 Conference Paper

Discrete Choice, Permutations, and Reconstruction

• Flavio Chierichetti
• Ravi Kumar 0001
• Andrew Tomkins

In this paper we study the well-known family of Random Utility Models, developed over 50 years ago to codify rational user behavior in choosing one item from a finite set of options. In this setting each user draws i. i. d. from some distribution a utility function mapping each item in the universe to a real-valued utility. The user is then offered a subset of the items, and selects the one of maximum utility. A M ax -D ist oracle for this choice model takes any subset of items and returns the probability (over the distribution of utility functions) that each will be selected. A discrete choice algorithm, given access to a M ax -D ist oracle, must return a function that approximates the oracle. We show three primary results. First, we show that any algorithm exactly reproducing the oracle must make exponentially many queries. Second, we show an equivalent representation of the distribution over utility functions, based on permutations, and show that if this distribution has support size k, then it is possible to approximate the oracle using O ( nk ) queries. Finally, we consider settings in which the subset of items is always small. We give an algorithm that makes less than n (1– ∊/ 2) K queries, each to sets of size at most (1– ∊/ 2) K, in order to approximate the M ax -D ist oracle on every set of size | T | ≤ K with statistical error at most ∊. In contrast, we show that any algorithm that queries for subsets of size must make maximal statistical error on some large sets.

ICML Conference 2018 Conference Paper

Learning a Mixture of Two Multinomial Logits

• Flavio Chierichetti
• Ravi Kumar 0001
• Andrew Tomkins

The classical Multinomial Logit (MNL) is a behavioral model for user choice. In this model, a user is offered a slate of choices (a subset of a finite universe of $n$ items), and selects exactly one item from the slate, each with probability proportional to its (positive) weight. Given a set of observed slates and choices, the likelihood-maximizing item weights are easy to learn at scale, and easy to interpret. However, the model fails to represent common real-world behavior. As a result, researchers in user choice often turn to mixtures of MNLs, which are known to approximate a large class of models of rational user behavior. Unfortunately, the only known algorithms for this problem have been heuristic in nature. In this paper we give the first polynomial-time algorithms for exact learning of uniform mixtures of two MNLs. Interestingly, the parameters of the model can be learned for any $n$ by sampling the behavior of random users only on slates of sizes 2 and 3; in contrast, we show that slates of size 2 are insufficient by themselves.

NeurIPS Conference 2018 Conference Paper

Mallows Models for Top-k Lists

• Flavio Chierichetti
• Anirban Dasgupta
• Shahrzad Haddadan
• Ravi Kumar
• Silvio Lattanzi

The classic Mallows model is a widely-used tool to realize distributions on per- mutations. Motivated by common practical situations, in this paper, we generalize Mallows to model distributions on top-k lists by using a suitable distance measure between top-k lists. Unlike many earlier works, our model is both analytically tractable and computationally efficient. We demonstrate this by studying two basic problems in this model, namely, sampling and reconstruction, from both algorithmic and experimental points of view.

ICML Conference 2017 Conference Paper

Algorithms for $\ell_p$ Low-Rank Approximation

• Flavio Chierichetti
• Sreenivas Gollapudi
• Ravi Kumar 0001
• Silvio Lattanzi
• Rina Panigrahy
• David P. Woodruff

We consider the problem of approximating a given matrix by a low-rank matrix so as to minimize the entrywise $\ell_p$-approximation error, for any $p \geq 1$; the case $p = 2$ is the classical SVD problem. We obtain the first provably good approximation algorithms for this robust version of low-rank approximation that work for every value of $p$. Our algorithms are simple, easy to implement, work well in practice, and illustrate interesting tradeoffs between the approximation quality, the running time, and the rank of the approximating matrix.

NeurIPS Conference 2017 Conference Paper

Fair Clustering Through Fairlets

• Flavio Chierichetti
• Ravi Kumar
• Silvio Lattanzi
• Sergei Vassilvitskii

We study the question of fair clustering under the {\em disparate impact} doctrine, where each protected class must have approximately equal representation in every cluster. We formulate the fair clustering problem under both the k-center and the k-median objectives, and show that even with two protected classes the problem is challenging, as the optimum solution can violate common conventions---for instance a point may no longer be assigned to its nearest cluster center! En route we introduce the concept of fairlets, which are minimal sets that satisfy fair representation while approximately preserving the clustering objective. We show that any fair clustering problem can be decomposed into first finding good fairlets, and then using existing machinery for traditional clustering algorithms. While finding good fairlets can be NP-hard, we proceed to obtain efficient approximation algorithms based on minimum cost flow. We empirically demonstrate the \emph{price of fairness} by quantifying the value of fair clustering on real-world datasets with sensitive attributes.

FOCS Conference 2015 Conference Paper

Approximate Modularity

• Flavio Chierichetti
• Abhimanyu Das
• Anirban Dasgupta 0001
• Ravi Kumar 0001

A set function on a ground set of size n is approximately modular if it satisfies every modularity requirement to within an additive error, approximate modularity is the set analog of approximate linearity. In this paper we study how close, in additive error, can approximately modular functions be to truly modular functions. We first obtain a polynomial time algorithm that makes O(n 2 log n) queries to any approximately modular function to reconstruct a modular function that is O(√n)-close. We also show an almost matching lower bound: any algorithm world need super polynomially many queries to construct a modular function that is o(√(n/log n))-close. In a striking contrast to these near-tight computational reconstruction bounds, we then show that for any approximately modular function, there exists a modular function that is O(log n)-close.

SODA Conference 2014 Conference Paper

Learning Entangled Single-Sample Gaussians

• Flavio Chierichetti
• Anirban Dasgupta 0001
• Ravi Kumar 0001
• Silvio Lattanzi

We introduce a new model of Gaussian mixtures, motivated by the setting where the data points correspond to ratings on a set of items provided by users who have widely varying expertise, and each user can rate an item at most once. In this mixture model, each item i has a true quality μ i, each user has a variance (lack of expertise), and the rating of a user j on an item i consists of a single sample independently drawn from the Normal distribution. The aim is to learn the unknown item qualities μ i 's as precisely as possible. We study the single item case and obtain efficient algorithms for the problem, complemented by near-matching lower bounds; we also obtain preliminary results for the multiple items case. !TEX root = paper. tex

TCS Journal 2014 Journal Article

The complexity of LSH feasibility

• Flavio Chierichetti
• Ravi Kumar
• Mohammad Mahdian

In this paper we study the complexity of the following feasibility problem: given an n × n similarity matrix S as input, is there a locality sensitive hash (LSH) for S? We show that the LSH feasibility problem is NP-hard even in the following strong promise version: either S admits an LSH or S is at ℓ 1 -distance at least n 2 − ϵ from every similarity that admits an LSH. We complement this hardness result by providing an O ˜ ( 3 n ) algorithm for the LSH feasibility problem, which improves upon the naïve n Θ ( n ) time algorithm; we prove that this running time is tight, modulo constants, under the Exponential Time Hypothesis.

SODA Conference 2012 Conference Paper

LSH-preserving functions and their applications

• Flavio Chierichetti
• Ravi Kumar 0001

SODA Conference 2012 Conference Paper

Voting with limited information and many alternatives

• Flavio Chierichetti
• Jon M. Kleinberg

FOCS Conference 2011 Conference Paper

Markov Layout

• Flavio Chierichetti
• Ravi Kumar 0001
• Prabhakar Raghavan

Consider the problem of laying out a set of n images that match a query onto the nodes of a √n×√n grid. We are given a score for each image, as well as the distribution of patterns by which a user's eye scans the nodes of the grid and we wish to maximize the expected total score of images selected by the user. This is a special case of the Markov layout problem, in which we are given a Markov chain M together with a set of objects to be placed at the states of the Markov chain. Each object has a utility to the user if viewed, as well as a stopping probability with which the user ceases to look further at objects. This layout problem is prototypical in a number of applications in web search and advertising, particularly in an emerging genre of search results pages from major engines. In a different class of applications, the states of the Markov chain are web pages at a publishers website and the objects are advertisements. We study the approximability of the Markov layout problem. Our main result is an O(log n) approximation algorithm for the most general version of the problem. The core idea is to transform an optimization problem over partial permutations into an optimization problem over sets by losing a logarithmic factor in approximation, the latter problem is then shown to be sub modular with two matroid constraints, which admits a constant-factor approximation. In contrast, we also show the problem is APX-hard via a reduction from CUBIC MAX-BISECTION. We then study harder variants of greater practical interest of the problem in which no gaps - states of M with no object placed on them - are allowed. By exploiting the geometry, we obtain an O(log 3/2 n) approximation algorithm when the digraph underlying M is a grid and an O(log n) approximation algorithm when it is a tree. These special cases are especially appropriate for our applications.

NeurIPS Conference 2011 Conference Paper

Reconstructing Patterns of Information Diffusion from Incomplete Observations

• Flavio Chierichetti
• David Liben-Nowell
• Jon Kleinberg

Motivated by the spread of on-line information in general and on-line petitions in particular, recent research has raised the following combinatorial estimation problem. There is a tree T that we cannot observe directly (representing the structure along which the information has spread), and certain nodes randomly decide to make their copy of the information public. In the case of a petition, the list of names on each public copy of the petition also reveals a path leading back to the root of the tree. What can we conclude about the properties of the tree we observe from these revealed paths, and can we use the structure of the observed tree to estimate the size of the full unobserved tree T? Here we provide the first algorithm for this size estimation task, together with provable guarantees on its performance. We also establish structural properties of the observed tree, providing the first rigorous explanation for some of the unusual structural phenomena present in the spread of real chain-letter petitions on the Internet.

TCS Journal 2011 Journal Article

Rumor spreading in social networks

• Flavio Chierichetti
• Silvio Lattanzi
• Alessandro Panconesi

Social networks are an interesting class of graphs likely to become of increasing importance in the future, not only theoretically, but also for its probable applications to ad hoc and mobile networking. Rumor spreading is one of the basic mechanisms for information dissemination in networks; its relevance stemming from its simplicity of implementation and effectiveness. In this paper, we study the performance of rumor spreading in the classic preferential attachment model of Bollobás et al. which is considered to be a valuable model for social networks. We prove that, in these networks: (a) The standard PUSH–PULL strategy delivers the message to all nodes within O ( log 2 n ) rounds with high probability; (b) by themselves, PUSH and PULL require polynomially many rounds. (These results are under the assumption that m, the number of new links added with each new node is at least 2. If m = 1 the graph is disconnected with high probability, so no rumor spreading strategy can work.) Our analysis is based on a careful study of some new properties of preferential attachment graphs which could be of independent interest.

STOC Conference 2010 Conference Paper

Almost tight bounds for rumour spreading with conductance

• Flavio Chierichetti
• Silvio Lattanzi
• Alessandro Panconesi

We show that if a connected graph with $n$ nodes has conductance φ then rumour spreading, also known as randomized broadcast, successfully broadcasts a message within ~O(φ -1 • log n), many rounds with high probability, regardless of the source, by using the PUSH-PULL strategy. The ~O(••) notation hides a polylog φ -1 factor. This result is almost tight since there exists graph of n nodes, and conductance φ, with diameter Ω(φ -1 • log n). If, in addition, the network satisfies some kind of uniformity condition on the degrees, our analysis implies that both both PUSH and PULL, by themselves, successfully broadcast the message to every node in the same number of rounds.

SODA Conference 2010 Conference Paper

Finding the Jaccard Median

• Flavio Chierichetti
• Ravi Kumar 0001
• Sandeep Pandey
• Sergei Vassilvitskii

SODA Conference 2010 Conference Paper

Rumour Spreading and Graph Conductance

• Flavio Chierichetti
• Silvio Lattanzi
• Alessandro Panconesi

FOCS Conference 2009 Conference Paper

Models for the Compressible Web

• Flavio Chierichetti
• Ravi Kumar 0001
• Silvio Lattanzi
• Alessandro Panconesi
• Prabhakar Raghavan

Graphs resulting from human behavior (the web graph, friendship graphs, etc.) have hitherto been viewed as a monolithic class of graphs with similar characteristics; for instance, their degree distributions are markedly heavy-tailed. In this paper we take our understanding of behavioral graphs a step further by showing that an intriguing empirical property of web graphs-their compressibility-cannot be exhibited by well-known graph models for the web and for social networks. We then develop amore nuanced model for web graphs and show that it does exhibit compressibility, in addition to previously modeled web graph properties.