Noticias en español
Constructions of circuits for the majority function.
Abstract: We will consider a task of computing the majority function by Boolean circuits. This function has logarithmic-depth circuits. Moreover, this remains true when circuits consist of just binary AND and OR, no negations. However, in this regime, no simultaneously explicit and “simple” construction is known (with “simple” being an informal property, referencing a subjective expositional complexity of a construction). In the talk, I will present a small piece of progress towards getting such a construction, and I will probably explain some classical constructions...
Read MoreConvergence Analysis of Davis-Yin Splitting via Scaled Relative Graphs.
Abstract: Davis-Yin splitting (DYS) has found a wide range of applications in optimization, but its linear rates of convergence have not been studied extensively. The scaled relative graph (SRG) simplifies the convergence analysis of operator splitting methods by mapping the action of the operator onto the complex plane, but the prior SRG theory did not fully apply to the DYS operator. In this work, we formalize an SRG theory for the DYS operator and use it to obtain tighter contraction factors.
Read MorePrecedence 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 More