Arrow Research search

Author name cluster

Alessandro Panconesi

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

21 papers
2 author rows

Possible papers

21

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.

PDF Details DOI

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.

Details

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.

PDF Details

TCS Journal 2020 Journal Article

Tracks from hell — When finding a proof may be easier than checking it

  • Matteo Almanza
  • Stefano Leucci
  • Alessandro Panconesi

We consider the popular smartphone game Trainyard: a puzzle game that requires the player to lay down tracks in order to route colored trains from departure stations to suitable arrival stations. While it is already known [Almanza et al. , FUN 2016] that the problem of finding a solution to a given Trainyard instance (i. e. , game level) is NP-hard, determining the computational complexity of checking whether a candidate solution (i. e. , a track layout) solves the level was left as an open problem. In this paper we prove that this verification problem is PSPACE-complete, thus implying that Trainyard players might not only have a hard time finding solutions to a given level, but they might even be unable to efficiently recognize them.

Details DOI

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.

PDF Details

TCS Journal 2018 Journal Article

Trainyard is NP-Hard

  • Matteo Almanza
  • Stefano Leucci
  • Alessandro Panconesi

Recently, due to the widespread diffusion of smart-phones, mobile puzzle games have experienced a huge increase in their popularity. A successful puzzle has to be both captivating and challenging, and it has been suggested that these features are somehow related to their computational complexity [6]. Indeed, many puzzle games – such as Mah-Jongg, Sokoban, Candy Crush, and 2048, to name a few – are known to be NP-hard [3, 4, 8, 12]. In this paper we consider Trainyard: a popular mobile puzzle game whose goal is to get colored trains from their initial stations to suitable destination stations. We prove that the problem of determining whether there exists a solution to a given Trainyard level is NP-hard. We also provide an implementation of our hardness reduction.

Details DOI

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.

Details DOI

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.

Details

TCS Journal 1998 Journal Article

Near-optimal, distributed edge colouring via the nibble method

  • Devdatt Dubhashi
  • David A. Grable
  • Alessandro Panconesi

We give a distributed randomized algorithm for graph edge colouring. Let G be a Δ-regular graph with n nodes. Here we prove: • • If ε>0 is fixed and Δ⪢log n, the algorithm almost always colours G with (1 + ε)Δ colours in time O(log n). • • If s>0 is fixed, there exists a positive constant k such that if Δ⪢log k n, the algorithm almost always colours G with Δ + Δ/log s n colours in time O(log n + log s n log log n). By “almost always” we mean that the algorithm may either use more than the claimed number of colours or run longer than the claimed time, but that the probability that either of these sorts of failure occurs can be made arbitrarily close to 0. The algorithm is based on the nibble method, a probabilistic strategy introduced by Vojtěch Rödl. The analysis makes use of a powerful large deviation inequality for functions of independent random variables.

Details DOI

TCS Journal 1998 Journal Article

On the hardness of allocating frequencies for hybrid networks

  • Ewa Malesińska
  • Alessandro Panconesi

This paper studies the channel stability number, a combinatorial function that has been introduced for evaluating frequency allocation plans for hybrid cellular networks. We present several results concerning the approximability of this function in the case of complete graphs and analyze how different constraints influence its computational complexity.

Details DOI

TCS Journal 1993 Journal Article

Quantifiers and approximation

  • Alessandro Panconesi
  • Desh Ranjan

We investigate the relationship between logical expressibility of NP optimization problems and their approximation properties. First such attempt was made by Papadimitrou and Yannakakis (1988), who defined the class of NPO problems MAX NP. We show that many important optimization problems do not belong to MAX NP and that, in fact, there are problems in P which are not in MAX NP. The problems that we consider fit naturally in a new complexity class that we call MAX Π1. We prove that several natural optimization problems are complete for MAX Π1 under approximation-preserving reductions. All these complete problems are not approximable unless P = NP. This motivates the definition of subclasses of MAX Π1 that only contain problems which are presumably eaiser with respect to approximation. In particular, the class that we call RMAX(2) contains approximable problems and problems like MAX CLIQUE that are not known to be nonapproximable. We prove the MAX CLIQUE and several other optimization problems are complete for RMAX(2). All the complete problems in RMAX(2) share the interesting property that they either are nonapproximable or are approximable to any degree of accuracy.

Details DOI

I&C Journal 1991 Journal Article

Completeness in approximation classes

  • Pierluigi Crescenzi
  • Alessandro Panconesi

We introduce a formal framework for studying approximation properties of NP optimization (NPO) problems. The classes of approximable problems we consider are those appearing in the literature, namely the class of approximable problems within a constant ε (APX), and the class of problems having a polynomial time approximation scheme (PTAS). We define natural approximation preserving reductions and obtain completeness results in NPO, APX, and PTAS. A complete problem in a class cannot have stronger approximation properties unless P = NP. We also show that the degree structure of NPO allows intermediate degrees, that is, if P ≠ NP, there are problems which are neither complete nor belong to a lower class.

Details DOI