This paper introduces stronger notions for approximate single-source shortest-path distances and gives simple reductions to compute them from weaker standard notions of approximate distances. Strongly-approximate distances isolate, capture, and address the well-known barriers for using approximate distances algorithmically and their reductions directly address these barriers in a clean and modular manner. The reductions are model-independent and require only logO(1) n black-box approximate distance computations. They apply equally to parallel, distributed, and semi-streaming settings. Strongly (1+ε)-approximate distances are equivalent to exact distances in a (1+ε)-perturbed graph and approximately satisfy the subtractive triangle inequality. In directed graphs, this is sufficient to reduce even exact distance computation to arbitrary (1+ε)-approximate ones.

Abstract. Assume [Formula: see text] players are placed on [Formula: see text] vertices of a graph [Formula: see text]. The following game was introduced by Winkler: An adversary puts a hat on each player, where each hat has a color out of [Formula: see text] available colors. The players can see the hat of each of their neighbors in [Formula: see text] but cannot see their own hats. Using a predetermined guessing strategy, the players then simultaneously guess the color of their hats. The players win if at least one of them guesses correctly; otherwise, the adversary wins. The largest integer [Formula: see text] such that there is a winning strategy for the players is denoted by [Formula: see text], and this is called the hat guessing number of [Formula: see text]. Although this game has received much attention in recent years, not much is known about how the hat guessing number relates to other graph parameters. For instance, a natural open question is whether the hat guessing number can be bounded from above in terms of degeneracy. In this paper, we prove that the hat guessing number of a graph can be bounded from above in terms of a related notion, which we call strong degeneracy. We further give an exact characterization of graphs with bounded strong degeneracy. As a consequence, we significantly improve the best known upper bound on the hat guessing number of outerplanar graphs from [Formula: see text] to 40 and further derive upper bounds on the hat guessing number for any class of [Formula: see text]-free graphs with bounded expansion, such as the class of [Formula: see text]-free planar graphs; more generally, for [Formula: see text]-free graphs with bounded Hadwiger number or without a [Formula: see text]-subdivision; and for Erdős–Rényi random graphs with constant average degree.

Consider the following simple coloring algorithm for a graph on n vertices. Each vertex chooses a color from {1, ..., Δ(G) + 1} uniformly at random. While there exists a conflicted vertex choose one such vertex uniformly at random and recolor it with a randomly chosen color. This algorithm was introduced by Bhartia et al. [MOBIHOC'16] for channel selection in WIFI-networks. We show that this algorithm always converges to a proper coloring in expected O(n log Δ) steps, which is optimal and proves a conjecture of Chakrabarty and de Supinski [SOSA'20].

We consider a search problem on a 2-dimensional infinite grid with a single mobile agent. The goal of the agent is to find her way home, which is located in a grid cell chosen by an adversary. Initially, the agent is provided with an infinite sequence of instructions, that dictate the movements performed by the agent. Each instruction corresponds to a movement to an adjacent grid cell and the set of instructions can be a function of the initial locations of the agent and home. The challenge of our problem stems from faults in the movements made by the agent. In every step, with some constant probability 0 ≤ p ≤ 1, the agent performs a random movement instead of following the current instruction. This paper provides two results on this problem. First, we show that for some values of p, there does not exist any set of instructions that guide the agent home in finite expected time. Second, we complement this impossibility result with an algorithm that, for sufficiently small values of p, yields a finite expected hitting time for home. In particular, we show that for any p < 1, our approach gives a hitting rate that decays polynomially as a function of time. In that sense, our approach is far superior to a standard random walk in terms of hitting time. The main contribution and take-home message of this paper is to show that, for some value of 0.01139 … < p < 0.6554 …, there exists a phase transition on the solvability of the problem.

One of the central goals of Recurrent Neural Networks (RNNs) is to learn long-term dependencies in sequential data. Nevertheless, the most popular training method, Truncated Backpropagation through Time (TBPTT), categorically forbids learning dependencies beyond the truncation horizon. In contrast, the online training algorithm Real Time Recurrent Learning (RTRL) provides untruncated gradients, with the disadvantage of impractically large computational costs. Recently published approaches reduce these costs by providing noisy approximations of RTRL. We present a new approximation algorithm of RTRL, Optimal Kronecker-Sum Approximation (OK). We prove that OK is optimal for a class of approximations of RTRL, which includes all approaches published so far. Additionally, we show that OK has empirically negligible noise: Unlike previous algorithms it matches TBPTT in a real world task (character-level Penn TreeBank) and can exploit online parameter updates to outperform TBPTT in a synthetic string memorization task. Code available at GitHub.