Rafael Frongillo

Rafael Frongillo

Auto-generated profile, based on publicly available information

Rafael Frongillo

Department of Computer Science University of Colorado Boulder USA

Research Focus & Metrics

Academic Career Length

20Years (2007-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
7 November 2023 in SIAM Review
Verified
Journal Article
Closed access
RTRichard C. Tillquist
Richard C. Tillquist
RFRafael M. Frongillo
Rafael M. Frongillo
MLManuel Lladser
Manuel Lladser
The metric dimension of a graph is the smallest number of nodes required to identify all other nodes uniquely based on shortest path distances. Applications of metric dimension include discovering the source of a spread in a network, canonically labeling graphs, and embedding symbolic data in low-dimensional Euclidean spaces. This survey gives a self-contained introduction to metric dimension and an overview of the quintessential results and applications. We discuss methods for approximating the metric dimension of general graphs, and specific bounds and asymptotic behavior for deterministic and random families of graphs. We conclude with related concepts and directions for future work.

21 July 2016
Verified
Conference Paper
Open access
VSVictor Shnayder
Victor Shnayder
AAArpit Agarwal
Arpit Agarwal
RFRafael Frongillo
Rafael Frongillo
DPDavid C. Parkes
David C. Parkes
The problem of peer prediction is to elicit information from agents in settings without any objective ground truth against which to score reports. Peer prediction mechanisms seek to exploit correlations between signals to align incentives with truthful reports. A long-standing concern has been the possibility of uninformative equilibria. For binary signals, a multi-task mechanism achieves strong truthfulness, so that the truthful equilibrium strictly maximizes payoff. We characterize conditions on the signal distribution for which this mechanism remains strongly-truthful with non-binary signals, also providing a greatly simplified proof. We introduce the Correlated Agreement (CA) mechanism, which handles multiple signals and provides informed truthfulness: no strategy profile provides more payoff in equilibrium than truthful reporting, and the truthful equilibrium is strictly better than any uninformed strategy (where an agent avoids the effort of obtaining a signal). The CA mechanism is maximally strongly truthful, in that no mechanism in a broad class of mechanisms is strongly truthful on a larger family of signal distributions. We also give a detail-free version of the mechanism that removes any knowledge requirements on the part of the designer, using reports on many tasks to learn statistics while retaining epsilon-informed truthfulness.

1 January 2008 in SIAM Journal on Applied Dynamical Systems
Verified
Journal Article
Closed access
SDSarah Day
Sarah Day
RFRafael Frongillo
Rafael Frongillo
RTRodrigo Treviño
Rodrigo Treviño
The aim of this paper is to introduce a method for computing rigorous lower bounds for topological entropy. The topological entropy of a dynamical system measures the number of trajectories that separate in finite time and quantifies the complexity of the system. Our method relies on extending existing computational Conley index techniques for constructing semiconjugate symbolic dynamical systems. Besides offering a description of the dynamics, the constructed symbol system allows for the computation of a lower bound for the topological entropy of the original system. Our overall goal is to construct symbolic dynamics that yield a high lower bound for entropy. The method described in this paper is algorithmic and, although it is computational, yields mathematically rigorous results. For illustration, we apply the method to the Hénon map, where we compute a rigorous lower bound of 0.4320 for topological entropy.

4 November 2020 in Biometrika
Verified
Journal Article
Closed access
PDF file
RFRafael M Frongillo
Rafael M Frongillo
IKIan A Kash
Ian A Kash
Summary: A property, or statistical functional, is said to be elicitable if it minimizes the expected loss for some loss function. The study of which properties are elicitable sheds light on the capabilities and limitations of point estimation and empirical risk minimization. While recent work has sought to identify which properties are elicitable, here we investigate a more nuanced question: how many dimensions are required to indirectly elicit a given property? This number is called the elicitation complexity of the property. We lay the foundation for a general theory of elicitation complexity, which includes several basic results on how elicitation complexity behaves and the complexity of standard properties of interest. Building on this foundation, our main result gives tight complexity bounds for the broad class of Bayes risks. We apply these results to several properties of interest, including variance, entropy, norms and several classes of financial risk measures. The article concludes with a discussion and open questions.

1 January 2010
Verified
Book Chapter
Open access
PDF file
CDConstantinos Daskalakis
Constantinos Daskalakis
RFRafael Frongillo
Rafael Frongillo
CPChristos H. Papadimitriou
Christos H. Papadimitriou
GPGeorge Pierrakos
George Pierrakos
GVGregory Valiant
Gregory Valiant
Can learning algorithms find a Nash equilibrium? This is a natural question for several reasons. Learning algorithms resemble the behavior of players in many naturally arising games, and thus results on the convergence or non-convergence properties of such dynamics may inform our understanding of the applicability of Nash equilibria as a plausible solution concept in some settings. A second reason for asking this question is in the hope of being able to prove an impossibility result, not dependent on complexity assumptions, for computing Nash equilibria via a restricted class of reasonable algorithms. In this work, we begin to answer this question by considering the dynamics of the standard multiplicative weights update learning algorithms (which are known to converge to a Nash equilibrium for zero-sum games). We revisit a 3×3 game defined by Shapley [10] in the 1950s in order to establish that fictitious play does not converge in general games. For this simple game, we show via a potential function argument that in a variety of settings the multiplicative updates algorithm impressively fails to find the unique Nash equilibrium, in that the cumulative distributions of players produced by learning dynamics actually drift away from the equilibrium.

1 January 2011
Verified
Book Chapter
Closed access
PDF file
RFRafael M. Frongillo
Rafael M. Frongillo
GSGrant Schoenebeck
Grant Schoenebeck
OTOmer Tamuz
Omer Tamuz