Noticias en español
Precedence Constraint Matching.
Abstract: In the precedence-constrained perfect matching problem, one needs to incrementally build a matching, whereby the order in which edges join the matching is subject to precedence constraints. Given a graph G = (V, E), a precedence constraint is a pair (X, e) with e being an edge and X a set of vertices, meaning that e may only be added to the matching after covering at least one vertex in X. In this talk, I will introduce C-canonical precedence constraints, where an edge may join a matching if both end-vertices have (shortest path) distance at most C to the current matching. I will...
Read MoreAnalysis of the survival time of the SIRS process via expansion.
Abstract: We study the SIRS process—a continuous-time Markov chain modelling thespread of infections on graphs. In this model, vertices are eithersusceptible, infected, or recovered. Each infected vertex becomesrecovered at rate 1 and infects each of its susceptible neighbors independently at rate~$\lambda$, and each recovered vertex becomes susceptible at a rate~$\rho$, which we assume to be independent of the graph size. A central quantity of the SIRS process is the time until no vertex is infected, known as the survival time. Surprisingly though, to the best of our knowledge, all...
Read MoreLearning-augmented Assignment: Santa Claus does Load Balancing.
Abstract: Assignment problems are among the most well-studied in online algorithms. In these problems, a sequence of items arriving online must be assigned among a set of agents so as to optimize a given objective. This encompasses scheduling problems for minimizing makespan, p-norms, and other objectives, as well as fair division problems such as the Santa Claus problem and Nash welfare maximization. One common feature is that many of these problems are characterized by strong worst-case lower bounds in the online setting. To circumvent these impossibility results, recent research has...
Read MoreA sequential Stackelberg game for dynamic inspection problems.
Abstract: This talk considers a game where an inspection authority must verify that a set of operators adhere to a certain rule. The inspector has time to inspect only a few operators, and this must be done sequentially. The operators disclose the sequence of inspections as they occur. We will discuss variants of this sequential game. The talk focuses on the mathematical structure of the set of equilibria of this inspection game, where the inspector is a Stackelberg leader and is capable of performing exactly two inspections. A static and dynamic version of the game are analyzed. In the...
Read MoreAttention is Turing Complete.
Abstract: Alternatives to recurrent neural networks, in particular, architectures based on self-attention, are gaining momentum for processing input sequences. In spite of their relevance, the computational properties of such networks have not yet been fully explored. We study the computational power of the Transformer, one of the most paradigmatic architectures exemplifying self-attention. We show that the Transformer with hard-attention is Turing complete exclusively based on their capacity to compute and access internal dense representations of the data. Our study also reveals some...
Read MoreProphet Inequalities Require Only a Constant Number of Samples.
Abstract: In a prophet inequality problem, n independent random variables are presented to a gambler one by one. The gambler decides when to stop the sequence and obtains the most recent value as a reward. We evaluate a stopping rule by the worst-case ratio between its expected reward and the expectation of the maximum variable. Because of its connections with resource allocation and posted-price mechanisms, this problem has been intensively studied, and several variants have been introduced. While most of the literature assumes that distributions are known to the gambler, recent work has...
Read More