APAlessandro Panconesi

Alessandro Panconesi

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Alessandro Panconesi has a total of 37 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    User choice, hidden gems, and the quadratic horizon

    by Flavio Chierichetti, Mirko Giacchini, Ravi Kumar, Alessandro Panconesi, Andrew Tomkins

    Content platforms typically engage with their users through small recommendation sets of items drawn from an extensive catalog. These sets are curated using machine-learned models optimized to present choices most likely to align with user preferences. We present surprising findings about such platforms. Even with complete information on user preferences within sets of up to k items, these models can only predict preferences within a “quadratic horizon” of k2 items and might fail to identify the best items in larger sets. To illustrate, we present striking examples where a platform interacting with users through small item sets, despite knowing that one item is favored by millions of users, cannot identify this item with better than random chance. Through both theoretical analysis and studies across various datasets, we demonstrate that “hidden gems,” items preferred by many users but invisible to platforms, exist in real-world datasets of moderate size, highlighting a significant gap in current recommendation platforms.

  • Open Access

    Learning Multinomial Logits in $O(n \log n)$ time

    by Flavio Chierichetti, Mirko Giacchini, Ravi Kumar, Silvio Lattanzi, Alessandro Panconesi, Erasmo Tani, Andrew Tomkins

    A Multinomial Logit (MNL) model is composed of a finite universe of items $[n]=\{1,..., n\}$, each assigned a positive weight. A query specifies an admissible subset -- called a slate -- and the model chooses one item from that slate with probability proportional to its weight. This query model is also known as the Plackett-Luce model or conditional sampling oracle in the literature. Although MNLs have been studied extensively, a basic computational question remains open: given query access to slates, how efficiently can we learn weights so that, for every slate, the induced choice distribution is within total variation distance $\varepsilon$ of the ground truth? This question is central to MNL learning and has direct implications for modern recommender system interfaces. We provide two algorithms for this task, one with adaptive queries and one with non-adaptive queries. Each algorithm outputs an MNL $M'$ that induces, for each slate $S$, a distribution $M'_S$ on $S$ that is within $\varepsilon$ total variation distance of the true distribution. Our adaptive algorithm makes $O\left(\frac{n}{\varepsilon^{3}}\log n\right)$ queries, while our non-adaptive algorithm makes $O\left(\frac{n^{2}}{\varepsilon^{3}}\log n \log\frac{n}{\varepsilon}\right)$ queries. Both algorithms query only slates of size two and run in time proportional to their query complexity. We complement these upper bounds with lower bounds of $Ω\left(\frac{n}{\varepsilon^{2}}\log n\right)$ for adaptive queries and $Ω\left(\frac{n^{2}}{\varepsilon^{2}}\log n\right)$ for non-adaptive queries, thus proving that our adaptive algorithm is optimal in its dependence on the support size $n$, while the non-adaptive one is tight within a $\log n$ factor.

  • Open Access

    A Topology-Based Approach for Predicting Toxic Outcomes on Twitter and YouTube

    by Gabriele Etta, Matteo Cinelli, Niccolò Di Marco, Michele Avalle, Alessandro Panconesi, Walter Quattrociocchi

    The benefits of an information ecosystem based on social media platforms came at the cost of the rise of several antisocial behaviours, including the use of toxic speech. To assess the aspects that concur with the formation of toxic conversations, we provide a multi-platform comparison on Twitter and YouTube between the 2022 Italian Political Elections, representing a potentially polarising topic, and the Italian Football League, a topic close to the country's popular culture. We first probe structural and conversational toxicity differences by analyzing 257 K conversations (3.7 M posts, 1 M users) on both platforms. Then, we provide a machine learning approach that, by leveraging the previous features, identifies the presence of the following toxic comment in different stages of conversations. We show that football tends to exhibit lower toxicity levels than politics, with the latter producing more extended conversations that attract a broader audience and consequently fostering the polarization phenomenon. The implemented classifiers resulting from the conversation stage-based approach achieve state-of-the-art performances despite a restricted set of features. Furthermore, our cross-topic comparison shows that models trained on a divisive topic can be applied to other discussions without causing a degradation of their performance.


  • Open Access

    Errare humanum est, perseverare autem diabolicum

    by Beatrice Biancardi, Enrico Lauletta, Antonio Norelli, Alessandro Panconesi, Maurizio Mancini

    Othello, also known as Reversi, is a popular 2-players board game. Olivaw is an intelligent agent playing Othello. Compared to the most famous ones (such as Saio), it exploits limited resources by autonomously learning how to improve its gameplay by playing against itself. In previous occasions, Othello players reported the impression of a sort of human-likeness in how Olivaw plays. We designed and ran an experimental study to better investigate these impressions in a controlled setting. Participants were asked to watch the moves of pre-recorded Othello games played by a human expert player against either another agent (i.e., Olivaw, Saio) or another human. The identity of the opponent, the outcome of the game (i.e., whether the human expert or the opponent player won), and the color of the players (i.e., black or white, black always playing first) were manipulated. We then asked participants to evaluate the human-likeness of the opponent player. Results confirm that the outcome of the match affects the perception of human-likeness of the players.

  • Olivaw: Mastering Othello Without Human Knowledge, nor a Fortune

    by Antonio Norelli, Alessandro Panconesi

    We introduce OLIVAW, an AI Othello player adopting the design principles of the famous AlphaGo programs. The main motivation behind OLIVAW was to attain exceptional competence in a non-trivial board game at a tiny fraction of the cost of its illustrious predecessors. In this paper, we show how the AlphaGo Zero's paradigm can be successfully applied to the popular game of Othello using only commodity hardware and free cloud services. While being simpler than Chess or Go, Othello maintains a considerable search space and difficulty in evaluating board positions. To achieve this result, OLIVAW implements some improvements inspired by recent works to accelerate the standard AlphaGo Zero learning process. The main modification implies doubling the positions collected per game during the training phase, by including also positions not played but largely explored by the agent. We tested the strength of OLIVAW in three different ways: by pitting it against Edax, the strongest open-source Othello engine, by playing anonymous games on the web platform OthelloQuest, and finally in two in-person matches against top-notch human players: a national champion and a former world champion.


  • Open Access

    Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models

    by Flavio Chierichetti, Alessandro Panconesi, Giuseppe Re, Luca Trevisan

    Correlation Clustering is an important clustering problem with many applications. We study the reconstruction version of this problem in which one is seeking to reconstruct a latent clustering that has been corrupted by random noise and adversarial modifications. Concerning the latter, there is a standard "post-adversarial" model in the literature, in which adversarial modifications come after the noise. Here, we introduce and analyse a "pre-adversarial" model in which adversarial modifications come before the noise. Given an input coming from such a semi-adversarial generative model, the goal is to reconstruct almost perfectly and with high probability the latent clustering. We focus on the case where the hidden clusters have nearly equal size and show the following. In the pre-adversarial setting, spectral algorithms are optimal, in the sense that they reconstruct all the way to the information-theoretic threshold beyond which no reconstruction is possible. This is in contrast to the post-adversarial setting, in which their ability to restore the hidden clusters stops before the threshold, but the gap is optimally filled by SDP-based algorithms. These results highlight a heretofore unknown robustness of spectral algorithms, showing them less brittle than previously thought.

  • Open Access

    Faster motif counting via succinct color coding and adaptive sampling

    by Marco Bressan, Stefano Leucci, Alessandro Panconesi

    We address the problem of computing the distribution of induced connected subgraphs, aka \emph{graphlets} or \emph{motifs}, in large graphs. The current state-of-the-art algorithms estimate the motif counts via uniform sampling, by leveraging the color coding technique by Alon, Yuster and Zwick. In this work we extend the applicability of this approach, by introducing a set of algorithmic optimizations and techniques that reduce the running time and space usage of color coding and improve the accuracy of the counts. To this end, we first show how to optimize color coding to efficiently build a compact table of a representative subsample of all graphlets in the input graph. For $8$-node motifs, we can build such a table in one hour for a graph with $65$M nodes and $1.8$B edges, which is $2000$ times larger than the state of the art. We then introduce a novel adaptive sampling scheme that breaks the "additive error barrier" of uniform sampling, guaranteeing multiplicative approximations instead of just additive ones. This allows us to count not only the most frequent motifs, but also extremely rare ones. For instance, on one graph we accurately count nearly $10.000$ distinct $8$-node motifs whose relative frequency is so small that uniform sampling would literally take centuries to find them. Our results show that color coding is still the most promising approach to scalable motif counting.

  • Trainyard is NP-Hard

    by Matteo Almanza, Stefano Leucci, Alessandro Panconesi


  • The One Million Dollars Problem

    by Alessandro Panconesi