14 citations · 27 across the 28 of their papers we have counts for
9 papers · 1 filter
Computational complexity of problems for deterministic presentations of sofic shifts
Justin Cai, Rafael Frongillo
Sofic shifts are symbolic dynamical systems defined by the set of bi-infinite sequences on an edge-labeled directed graph, called a presentation. We study the computational complex…
Agreement Implies Accuracy for Substitutable Signals
Rafael Frongillo, Eric Neyman, Bo Waggoner
Inspired by Aumann's agreement theorem, Scott Aaronson studied the amount of communication necessary for two Bayesian experts to approximately agree on the expectation of a random…
Surrogate Regret Bounds for Polyhedral Losses
Rafael Frongillo, Bo Waggoner
Surrogate risk minimization is an ubiquitous paradigm in supervised machine learning, wherein a target problem is solved by minimizing a surrogate loss on a dataset. Surrogate regr…
Graphical Economies with Resale
Gabriel P. Andrade, Rafael Frongillo, Elliot Gorokhovsky +1
Kakade, Kearns, and Ortiz (KKO) introduce a graph-theoretic generalization of the classic Arrow--Debreu (AD) exchange economy. Despite its appeal as a networked version of AD, we a…
Truncated Metric Dimension for Finite Graphs
Richard C. Tillquist, Rafael M. Frongillo, Manuel E. Lladser
A graph with geodesic distance is said to be resolved by a non-empty subset of its vertices when, for all vertices and , if fo…
Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and its Applications
Richard C. Tillquist, Rafael M. Frongillo, Manuel E. Lladser
The metric dimension of a graph is the smallest number of nodes required to identify all other nodes based on shortest path distances uniquely. Applications of metric dimension inc…