A number of engineering and scientific problems require representing and manipulating probability distributions over large alphabets, which we may think of as long vectors of reals summing to 1. In some cases it is required to represent such a vector with only b bits per entry. A natural choice is to partition the interval [0,1] into 2buniform bins and quantize entries to each bin independently. We show that a minor modification of this procedure – applying an entrywise non-linear function (compander) f(x) prior to quantization – yields an extremely effective quantization method. For example, for b = 8(16) and 105-sized alphabets, the quality of representation improves from a loss (under KL divergence) of 0.5(0.1) bits/entry to 10−4(10−9) bits/entry. Compared to floating point representations, our compander method improves the loss from 10−1(10−6) to 10−4(10−9) bits/entry. These numbers hold for both real-world data (word frequencies in books and DNA k-mer counts) and for synthetic randomly generated distributions. Theoretically, we set up a minimax optimality criterion and show that the compander $f(x) \propto \operatorname{ArcSinh} (\sqrt {(1/2)(K\log K)x} )$ achieves near-optimal performance, attaining a KL-quantization loss of ≍ 2−2blog2K for a K-letter alphabet and b →∞. Interestingly, a similar minimax criterion for the quadratic loss on the hypercube shows optimality of the standard uniform quantizer. This suggests that the ArcSinh quantizer is as fundamental for KL-distortion as the uniform quantizer for quadratic distortion.

Consider the problem of representing a distribution$\pi$on a large alphabet of size$k$up to fidelity$\varepsilon$in Kullback-Leibler (KL) divergence. Heuristically, arguing as for quadratic loss in high dimension, one expects that about$(k/2)\log(1/\varepsilon)$bits would be required. We show this intuition is correct by proving explicit non-asymptotic bounds for the minimal average distortion when$\pi$is randomly sampled from a symmetric Dirichlet prior on the simplex. Our method is to reduce the single-sample problem to the traditional setting of iid samples, but for a non-standard rate distortion question with the novel distortion measure$d(x, y)= x\log(x/y)$, which we call divergence distortion. Practically, our results advocate using a$x\mapsto x^{2/3}$compander (for small$x$) followed by a uniform scalar quantizer for storing large-alphabet distributions.

The Jordan curve theorem and Brouwer's fixed-point theorem are fundamental problems in topology. We study their computational relationship, showing that a stylized computational version of Jordan’s theorem is PPAD-complete, and therefore in a sense computationally equivalent to Brouwer’s theorem. As a corollary, our computational result implies that these two theorems directly imply each other mathematically, complementing Maehara's proof that Brouwer implies Jordan [Maehara, 1984]. We then turn to the combinatorial game of Hex which is related to Jordan's theorem, and where the existence of a winner can be used to show Brouwer's theorem [Gale,1979]. We establish that determining who won an (implicitly encoded) play of Hex is PSPACE-complete by adapting a reduction (due to Goldberg [Goldberg,2015]) from Quantified Boolean Formula (QBF). As this problem is analogous to evaluating the output of a canonical path-following algorithm for finding a Brouwer fixed point - and which is known to be PSPACE-complete [Goldberg/Papadimitriou/Savani, 2013] - we thereby establish a connection between Brouwer, Jordan and Hex higher in the complexity hierarchy.

In the classic Traveling Salesman Problem (TSP), the objective is to find the shortest path that visits a set of target locations. This problem is embedded and essential in many planning problems that arise in robotics, particularly in the domains of exploration, monitoring, surveillance, and reconnaissance. In this paper we consider the Stochastic TSP for Dynamical Systems, where a vehicle with complex dynamics is tasked with visiting n random target locations. By borrowing techniques from the applied probability literature, which were used to study the related stochastic Orienteering problem (where the vehicle has to visit as many of the n points as possible with a path of fixed length), we simplify and extend the existing results for both the TSP and the stochastic Orienteering problems to cases where the target points can be picked up only when the vehicle is in a certain configuration (i.e. it is not enough simply to be on the target point). Specifically, we show that there is a special parameter γ of the dynamics of the vehicle, which governs the length of the TSP tour. The length of the shortest path will then be Θ(n(γ-1)/γ) with very high probability. For stochastic Orienteering, if the path must have length at most λ, the vehicle can pick up Θ(λn1/γ) with very high probability. We also provide simple and efficient path planning algorithms which achieve these bounds, and are therefore within a constant factor of the length of the optimal path with very high probability.

We consider the following motion-planning problem: we are given \mbim unit discs in a simple polygon with \mbin vertices, each at their own start position, and we want to move the discs to a given set of \mbim target positions. Contrary to the standard (labeled) version of the problem, each disc is allowed to be moved to any target position, as long as in the end every target position is occupied. We show that this unlabeled version of the problem can be solved in \mbiO(m2+mn) time, assuming that the start and target positions are at least some minimal distance from each other. This is in sharp contrast to the standard (labeled) and more general multi-robot motion planning problem for discs moving in a simple polygon, which is known to be strongly NP-hard.

Metrology, the theoretical and practical study of measurement, has applications in automated manufacturing, inspection, robotics, surveying, and healthcare. The geometric probing problem considers how to optimally use a probe to measure geometric properties. In this paper, we consider a proximity probe which, given a point, returns the distance to the boundary of the nearest object. When there is an unknown convex polygon P in the plane, the goal is to minimize the number of probe measurement needed to exactly determine the shape and location of P. We present an algorithm with upper bound of 3.5n + k + 2 probes, where n is the number of vertices and k ≤ 3 is the number of acute angles of P. The algorithm requires constant time per probe, and hence, O(n) time to determine P. We also address the related problem where the unknown polygon is a member of a known finite set Γ and the goal is to efficiently determine which polygon is present. When m is the size of Γ and n' is the maximum number of vertices of any member of Γ, we present an algorithm with an upper bound of 2n + 2 probes with O(1) computations per probe and a O(n'm) preprocessing phase (depending only on Γ).