Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

We introduce synchronization strings , which provide a novel way to efficiently deal with synchronization errors , i.e., insertions and deletions. Synchronization errors are strictly more general and much harder to cope with than more commonly considered Hammingtype errors , i.e., symbol substitutions and erasures. For every ε > 0, synchronization strings allow us to index a sequence with an ε O(1) size alphabet, such that one can efficiently transform k synchronization errors into (1 + ε)k Hammingtype errors . This powerful new technique has many applications. In this article, we focus on designing insdel codes , i.e., error correcting block codes (ECCs) for insertiondeletion channels. While ECCs for both Hammingtype errors and synchronization errors have been intensely studied, the latter has largely resisted progress. As Mitzenmacher puts it in his 2009 survey [30]: “ Channels with synchronization errors...are simply not adequately understood by current theory. Given the nearcomplete knowledge, we have for channels with erasures and errors...our lack of understanding about channels with synchronization errors is truly remarkable. ” Indeed, it took until 1999 for the first insdel codes with constant rate, constant distance, and constant alphabet size to be constructed and only since 2016 are there constructions of constant rate insdel codes for asymptotically large noise rates. Even in the asymptotically large or small noise regimes, these codes are polynomially far from the optimal ratedistance tradeoff. This makes the understanding of insdel codes up to this work equivalent to what was known for regular ECCs after Forney introduced concatenated codes in his doctoral thesis 50 years ago. A straightforward application of our synchronization stringsbased indexing method gives a simple blackbox construction that transforms any ECC into an equally efficient insdel code with only a small increase in the alphabet size. This instantly transfers much of the highly developed understanding for regular ECCs into the realm of insdel codes. Most notably, for the complete noise spectrum, we obtain efficient “nearMDS” insdel codes, which get arbitrarily close to the optimal ratedistance tradeoff given by the Singleton bound. In particular, for any δ ∈ (0,1) and ε > 0, we give a family of insdel codes achieving a rate of 1  δ  ε over a constantsize alphabet that efficiently corrects a δ fraction of insertions or deletions.more » « less

null (Ed.)Many distributed optimization algorithms achieve existentiallyoptimal running times, meaning that there exists some pathological worstcase topology on which no algorithm can do better. Still, most networks of interest allow for exponentially faster algorithms. This motivates two questions: (i) What network topology parameters determine the complexity of distributed optimization? (ii) Are there universallyoptimal algorithms that are as fast as possible on every topology? We resolve these 25yearold open problems in the knowntopology setting (i.e., supported CONGEST) for a wide class of global network optimization problems including MST, (1+є)min cut, various approximate shortest paths problems, subgraph connectivity, etc. In particular, we provide several (equivalent) graph parameters and show they are tight universal lower bounds for the above problems, fully characterizing their inherent complexity. Our results also imply that algorithms based on the lowcongestion shortcut framework match the above lower bound, making them universally optimal if shortcuts are efficiently approximable.more » « less

null (Ed.)Network design problems aim to compute lowcost structures such as routes, trees and subgraphs. Often, it is natural and desirable to require that these structures have small hop length or hop diameter. Unfortunately, optimization problems with hop constraints are much harder and less well understood than their hopunconstrained counterparts. A significant algorithmic barrier in this setting is the fact that hopconstrained distances in graphs are very far from being a metric. We show that, nonetheless, hopconstrained distances can be approximated by distributions over ``partial tree metrics.'' We build this result into a powerful and versatile algorithmic tool which, similarly to classic probabilistic tree embeddings, reduces hopconstrained problems in general graphs to hopunconstrained problems on trees. We then use this tool to give the first polylogarithmic bicriteria approximations for the hopconstrained variants of many classic network design problems. These include Steiner forest, group Steiner tree, group Steiner forest, buyatbulk network design as well as online and oblivious versions of many of these problems.more » « less

null (Ed.)We prove the existence of an oblivious routing scheme that is poly(logn)competitive in terms of (congestion + dilation), thus resolving a wellknown question in oblivious routing. Concretely, consider an undirected network and a set of packets each with its own source and destination. The objective is to choose a path for each packet, from its source to its destination, so as to minimize (congestion + dilation), defined as follows: The dilation is the maximum path hoplength, and the congestion is the maximum number of paths that include any single edge. The routing scheme obliviously and randomly selects a path for each packet independent of (the existence of) the other packets. Despite this obliviousness, the selected paths have (congestion + dilation) within a poly(logn) factor of the best possible value. More precisely, for any integer hopbound h, this oblivious routing scheme selects paths of length at most h · poly(logn) and is poly(logn)competitive in terms of congestion in comparison to the best possible congestion achievable via paths of length at most h hops. These paths can be sampled in polynomial time. This result can be viewed as an analogue of the celebrated oblivious routing results of R'acke [FOCS 2002, STOC 2008], which are O(logn)competitive in terms of congestion, but are not competitive in terms of dilation.more » « less