We consider the problem of solving integer programs of the form min {c^⊺ x : Ax = b, x ∈ ℤ_{⩾ 0}}, where A is a multistage stochastic matrix in the following sense: the primal treedepth of A is bounded by a parameter d, which means that the columns of A ca ...
Schloss Dagstuhl - Leibniz-Zentrum für Informatik2021
In the localization game on a graph, the goal is to find a fixed but unknown target node v* with the least number of distance queries possible. In the j-th step of the game, the player queries a single node v_j and receives, as an answer to their query, th ...
We show that a constant factor approximation of the shortest and closest lattice vector problem in any l(p)-norm can be computed in time 2((0.802 + epsilon)n). This matches the currently fastest constant factor approximation algorithm for the shortest vect ...
In this work, we introduce a setup where a monitoring entity attempts to distinguish a cheating player among a group of regular players where all players behave in order to maximize their reward. We assume that the cheating player has an "information advan ...
We construct (modified) scattering operators for the Vlasov–Poisson system in three dimensions, mapping small asymptotic dynamics as t→−∞ to asymptotic dynamics as t→+∞. The main novelty is the construction of modified wave operators, but we also obtain a ...
We study the basic problem of assigning memoryless workers to tasks with dynamically changing demands. Given a set of w workers and a multiset T ⊆ [t] of |T| = w tasks, a memoryless worker-task assignment function is any function ϕ that assigns the workers ...
Schloss Dagstuhl -- Leibniz-Zentrum fur Informatik2022
Graph sparsification has been studied extensively over the past two decades, culminating in spectral sparsifiers of optimal size (up to constant factors). Spectral hypergraph sparsification is a natural analogue of this problem, for which optimal bounds on ...
Understanding epidemic propagation in large networks is an important but challenging task, especially since we usually lack information, and the information that we have is often counter-intuitive. An illustrative example is the dependence of the final siz ...
We prove small data modified scattering for the Vlasov-Poisson system in dimension d=3 using a method inspired from dispersive analysis. In particular, we identify a simple asymptotic dynamic related to the scattering mass. ...
The design and implementation of efficient concurrent data structures has seen significant attention. However, most of this work has focused on concurrent data structures providing good worst-case guarantees, although, in real workloads, objects are often ...
