We revisit the problem of fault-tolerant (FT) distance preservers, when failure events in the network admit a form of correlation modeled as color faults. FT distance preservers are sparse subgraphs that preserve distances between specified pairs of vertices, even after some edge or vertex failures occur. In the classical fault model, any set of at most $k$ edges or vertices might fail (where $k \geq 1$ is a given parameter). Despite extensive research, the classical model admits significant and tantalizing gaps, both in terms of sparsity bounds and of algorithmic efficiency. In this work, we study the problem in the recently introduced color fault-tolerant (CFT) model: the given graph $G=(V,E)$ has arbitrary colors on its edges/vertices where each color appears at most $k$ times, and is susceptible to color faults, where the failure of color $c$ causes all the $c$-colored elements to crash. Our main contribution is in the multi-source setting, where $G$ has a source-set $S \subseteq V$, and the CFT preserver should preserve $S \times V$ distances under any single color fault. We show the following results (where $n = |V|$, $m = |E|$): - There exists a CFT distance preserver $H$ of $G$ with $\tilde{O}(n^{2 - \frac{1}{k+1}} \cdot |S|^{\frac{1}{k+1}} )$ edges. - The above sparsity bound is worst-case optimal up to polylogarithmic terms. - There is a combinatorial randomized algorithm that produces a preserver $H$ whose size meets the above optimal sparsity bound, with running time of $\tilde{O}(m \cdot n^{1 - \frac{1}{k+1}} \cdot |S|^{\frac{1}{k+1}})$. - The above running time is conditionally optimal: a polynomial improvement would refute the combinatorial Boolean Matrix Multiplication (BMM) conjecture. Furthermore, the running time remains optimal even if we only require mild sparsification to $m^{1-ε}$ edges.

We provide new communication-efficient distributed interactive proofs for planarity. The notion of a distributed interactive proof (DIP) was introduced by Kol, Oshman, and Saxena (PODC 2018). In a DIP, the prover is a single centralized entity whose goal is to prove a certain claim regarding an input graph \(G\). To do so, the prover communicates with a distributed verifier that operates concurrently on all \(n\) nodes of \(G\). A DIP is measured by the amount of prover-verifier communication it requires. Namely, the goal is to design a DIP with a small number of interaction rounds and a small proof size, i.e., a small amount of communication per round.

We study the succinct representations of vertex cuts by centralized oracles and labeling schemes. For an undirected \(n\)-vertex graph \(G = (V,E)\) and integer parameter \(f \ge 1\), the goal is supporting vertex cut queries: Given \(F \subseteq V\) with \(|F| \le f\), determine if \(F\) is a vertex cut in \(G\). In the centralized data structure setting, it is required to preprocess \(G\) into an \(f\)-vertex cut oracle that can answer such queries quickly, while occupying only small space. In the labeling setting, one should assign a short label to each vertex in \(G\), so that a cut query \(F\) can be answered by merely inspecting the labels assigned to the vertices in \(F\).

We present improved distributed broadcast and MST algorithms that are unconditionally secure against an eavesdropper controlling a fixed set of at most f edges in an n-node m-edge D-diameter graph. We strive for secure algorithms with sublinear round and subquadratic message complexities (in n) for any f. This is in contrast to the exponential or polynomial dependence on f in prior works. Our main results are:

Abstract. The paper presents fault-tolerant (FT) labeling schemes for general graphs, as well as improved FT routing schemes. For a given [Formula: see text]-vertex graph [Formula: see text] and a bound [Formula: see text] on the number of faults, an [Formula: see text]-FT connectivity labeling scheme is a distributed data structure that assigns to each of the graph edges and vertices a short label, such that given the labels of a vertex pair [Formula: see text] and [Formula: see text], and the labels of at most [Formula: see text] failing edges [Formula: see text], one can determine if [Formula: see text] and [Formula: see text] are connected in [Formula: see text]. The primary complexity measure is the length of the individual labels. Since their introduction by [Courcelle, Twigg, STACS ’07], compact FT labeling schemes have been devised only for a limited collection of graph families. In this work, we fill in this gap by proposing two (independent) FT connectivity labeling schemes for general graphs, with a nearly optimal label length. This serves the basis for providing also FT approximate distance labeling schemes, and ultimately also routing schemes. Our main results for an [Formula: see text]-vertex graph and a fault bound [Formula: see text] are (1) There is a randomized FT connectivity labeling scheme with a label length of [Formula: see text] bits, hence optimal for [Formula: see text]. This scheme is based on the notion of cycle space sampling [Pritchard, Thurimella, TALG ’11]. (2) There is a randomized FT connectivity labeling scheme with a label length of [Formula: see text] bits (independent of the number of faults [Formula: see text]). This scheme is based on the notion of linear sketches of [Ahn et al., SODA ’12]. (3) For a given stretch parameter [Formula: see text], there is a randomized routing scheme that routes a message from [Formula: see text] to [Formula: see text] in the presence of a set [Formula: see text] of faulty edges (unknown to [Formula: see text]) over a path of length [Formula: see text]. The routing labels have [Formula: see text] bits, the header size is [Formula: see text] bits, and each routing table has only [Formula: see text] bits. (Throughout the paper, we use the notation [Formula: see text] to hide poly-logarithmic in [Formula: see text] terms.) The results also hold for weighted graphs with positive polynomial weights. This significantly improves over the state-of-the-art bounds by [Chechik, ICALP ’11], providing the first scheme with sublinear FT labeling and routing schemes for general graphs.

The dual of a planar graph G is a planar graph G* that has a vertex for each face of G and an edge for each pair of adjacent faces of G. The profound relationship between a planar graph and its dual has been the algorithmic basis for solving numerous (centralized) classical problems on planar graphs involving distances, flows, and cuts. In the distributed setting however, the only use of planar duality is for finding a recursive decomposition of G [DISC 2017, STOC 2019].

Resilient computation in all-to-all-communication models has attracted tremendous attention over the years. Most of these works assume the classical faulty model which restricts the total number of corrupted edges (or vertices) by some integer fault parameter f. A recent work by [Bodwin, Haeupler and Parter, SODA 2024] introduced a stronger notion of fault-tolerance, in the context of graph sparsification, which restricts the degree of the failing edge set F, rather than its cardinality. For a subset of faulty edges F, the faulty-degree deg(F) is the largest number of faults in F incident to any given node.

We provide new distributed interactive proofs (DIP) for planarity and related graph families. The notion of a distributed interactive proof (DIP) was introduced by Kol, Oshman, and Saxena (PODC 2018). In this setting, the verifier consists of n nodes connected by a communication graph G. The prover is a single entity that communicates with all nodes by short messages. The goal is to verify that the graph G satisfies a certain property (e.g., planarity) in a small number of rounds, and with a small communication bound, denoted as the proof size.

A t-spanner of an undirected n-vertex graph G is a sparse subgraph H of G that preserves all pairwise distances between its vertices to within multiplicative factor t, also called the stretch. Spanners play an important role in the design of efficient algorithms for distance-based graph optimization problems, as they allow one to sparsify the graph, while approximately preserving all distances. It is well known that any n-vertex graph admits a (2k — 1)-spanner with O (n1+1/k) edges, and that this stretch-size tradeoff is optimal assuming the Erdos Girth Conjecture. In this paper we investigate the problem of efficiently maintaining spanners in the fully dynamic setting with an adaptive adversary. Despite a long and intensive line of research, this problem is still poorly understood: for example, no algorithm achieving a sublogarithmic stretch, with a sublinear in n update time, and a strongly subquadratic in n bound on the size of the spanner is currently known in this setting. One of our main results is a deterministic (and therefore, adaptive-adversary) algorithm, that, for any 512 ≤ k ≤ (log n )1/49 and 1/k ≤ δ ≤ 1/400, maintains a spanner H of a fully dynamic graph with stretch poly(k ) · 2o (1/δ6) and size |E (H )| ≤ O (n 1+O (1/k )), with worst-case update time n O(δ ) and recourse n O(1/k ).

An r-missing spanner for a graph G is a sparse subgraph H ⊆ G satisfying that for any u, v pair there is a (possibly approximate) u-v shortest path P in G such that |P \ H| ≤ r. That is, H misses at most r edges from every u-v (approximate) shortest path. [Kogan and Parter, FOCS ’22] introduced the notion of missing spanners as an intermediate step for translating hopset constructions into spanners and distance preservers.

We provide new algorithms for constructing spanners of arbitrarily edge- or vertex-colored graphs, that can endure up to f failures of entire color classes. The failure of even a single color may cause a linear number of individual edge/vertex faults. This model, related to the notion of hedge connectivity, arises in many practical contexts such as optical telecommunication and multi-layered networks.

We study a new and stronger notion of fault-tolerant graph structures whose size bounds depend on the degree of the failing edge set, rather than the total number of faults. For a subset of faulty edges F ⊆ G, the faulty-degree deg(F) is the largest number of faults in F incident to any given vertex. For example, a matching F has deg(F) = 1 while |F| might be as large as n/2.

We present succinct labeling schemes for answering connectivity queries in graphs subject to a specified number of vertex failures. An f-vertex/edge fault tolerant (f-V/EFT) connectivity labeling is a scheme that produces succinct labels for the vertices (and possibly to the edges) of an n-vertex graph G, such that given only the labels of two vertices s,t and of at most f faulty vertices/edges F, one can infer if s and t are connected in G−F. The primary complexity measure is the maximum label length (in bits). The f-EFT setting is relatively well understood: [Dory and Parter, PODC 2021] gave a randomized scheme with succinct labels of O(log3 n) bits, which was subsequently derandomized by [Izumi et al., PODC 2023] with Õ(f2)-bit labels. As both noted, handling vertex faults is more challenging. The known bounds for the f-VFT setting are far away: [Parter and Petruschka, DISC 2022] gave Õ(n1−1/2Θ(f))-bit labels, which is linear in n already for f =Ω(loglogn). In this work we present an efficient f-VFT connectivity labeling scheme using poly(f, logn) bits. Specifically, we present a randomized scheme with O(f3 log5 n)-bit labels, and a derandomized version with O(f7 log13 n)-bit labels, compared to an Ω(f)-bit lower bound on the required label length. Our schemes are based on a new low-degree graph decomposition that improves on [Duan and Pettie, SODA 2017], and facilitates its distributed representation into labels. This is accompanied with specialized linear graph sketches that extend the techniques of the Dory and Parter to the vertex fault setting, which are derandomized by adapting the approach of Izumi et al. and combining it with hit-miss hash families of [Karthik and Parter, SODA 2021]. Finally, we show that our labels naturally yield routing schemes avoiding a given set of at most f vertex failures with table and header sizes of only poly(f,logn) bits. This improves significantly over the linear size bounds implied by the EFT routing scheme of Dory and Parter.

Abstract In this paper, we study the power and limitations of component-stable algorithms in the low-space model of massively parallel computation (). Recently Ghaffari, Kuhn and Uitto (FOCS 2019) introduced the class of component-stable low-space algorithms, which are, informally, those algorithms for which the outputs reported by the nodes in different connected components are required to be independent. This very natural notion was introduced to capture most (if not all) of the known efficient algorithms to date, and it was the first general class of algorithms for which one can show non-trivial conditional lower bounds. In this paper we enhance the framework of component-stable algorithms and investigate its effect on the complexity of randomized and deterministic low-space . Our key contributions include: 1. We revise and formalize the lifting approach of Ghaffari, Kuhn and Uitto. This requires a very delicate amendment of the notion of component stability, which allows us to fill in gaps in the earlier arguments. 2. We also extend the framework to obtain conditional lower bounds for deterministic algorithms and fine-grained lower bounds that depend on the maximum degree $$\Delta $$ Δ . 3. We demonstrate a collection of natural graph problems for which deterministic component-unstable algorithms break the conditional lower bound obtained for component-stable algorithms. This implies that, in the context of deterministic algorithms, component-stable algorithms are conditionally weaker than the component-unstable ones. 4. We also show that the restriction to component-stable algorithms has an impact in the randomized setting. We present a natural problem which can be solved in O(1) rounds by a component-unstable algorithm, but requires $$\Omega (\log \log ^* n)$$ Ω ( log log ∗ n ) rounds for any component-stable algorithm, conditioned on the connectivity conjecture. Altogether our results imply that component-stability might limit the computational power of the low-space model, at least in certain contexts, paving the way for improved upper bounds that escape the conditional lower bound setting of Ghaffari, Kuhn, and Uitto.

In this article, we provide a unified and simplified approach to derandomize central results in the area of fault-tolerant graph algorithms. Given a graph \(G\) , a vertex pair \((s,t)\in V(G)\times V(G)\) , and a set of edge faults \(F\subseteq E(G)\) , a replacement path \(P(s,t,F)\) is an \(s\) - \(t\) shortest path in \(G\setminus F\) . For integer parameters \(L,f\) , a replacement path covering ( \(\mathsf{RPC}\) ) is a collection of subgraphs of \(G\) , denoted by \(\mathcal{G}_{L,f}=\{G_{1},\ldots,G_{r}\}\) , such that for every set \(F\) of at most \(f\) faults (i.e., \(|F|\leq f\) ) and every replacement path \(P(s,t,F)\) of at most \(L\) edges, there exists a subgraph \(G_{i}\in\mathcal{G}_{L,f}\) that contains all the edges of \(P\) and does not contain any of the edges of \(F\) . The covering value of the \(\mathsf{RPC}\) \(\mathcal{G}_{L,f}\) is then defined to be the number of subgraphs in \(\mathcal{G}_{L,f}\) . In the randomized setting, it is easy to build an \((L,f)\) - \(\mathsf{RPC}\) with covering value of \(O(\max\{L,f\}^{\min\{L,f\}}\cdot\min\{L,f\}\cdot \log n)\) , but to this date, there is no efficient deterministic algorithm with matching bounds. As noted recently by Alon et al. (ICALP 2019), this poses the key barrier for derandomizing known constructions of distance sensitivity oracles and fault-tolerant spanners. We show the following: — There exist efficient deterministic constructions of \((L,f)\) - \(\mathsf{RPC}\) s whose covering values almost match the randomized ones, for a wide range of parameters. Our time and value bounds improve considerably over the previous construction of Parter (DISC 2019). Our algorithms are based on the introduction of a novel notion of hash families that we call HM hash families. We then show how to construct these hash families from (algebraic) error correcting codes such as Reed–Solomon codes and Algebraic-Geometric codes. — For every \(L,f\) , and \(n\) , there exists an \(n\) -vertex graph \(G\) whose \((L,f)\) - \(\mathsf{RPC}\) covering value is \(\Omega(L^{f})\) . This lower bound is obtained by exploiting connections to the problem of designing sparse fault-tolerant breadth first search (BFS) structures. An application of our above deterministic constructions is the derandomization of the algebraic construction of the distance sensitivity oracle by Weimann and Yuster (FOCS 2010). The preprocessing and query time of our deterministic algorithm nearly match the randomized bounds. This resolves the open problem of Alon et al. (ICALP 2019). Additionally, we show a derandomization of the randomized construction of vertex fault-tolerant spanners by Dinitz and Krauthgamer (PODC 2011) and Braunschvig et al. (Theor. Comput. Sci., 2015). The time complexity and the size bounds of the output spanners near

We present a new algorithmic approach to distributed secure algorithms that is based on combining two independent lines of research: secure computation and distributed universal optimality. Our end result provides round-efficient distributed algorithms that protect the privacy of the graph vertices against a (possibly large) coalition of semi-honest adversaries.Secure Computation: The notion of perfect privacy dates back to Yao [FOCS ’82], and has been extensively addressed by the Cryptographic community over the years. Most of the prior work considers the Multi-Party-Communication (MPC) model, in which the parties are fully connected. Considerably less is known on the (round) complexity of secure algorithms for general graphs, especially under the classical message passing models, such as the CONGEST model. For any biconnected D-diameter graph, a recent line of works [Parter and Yogev, SODA 19, ICALP 19, PODC 19] presented a simulation result that protects against a single semi-honest corruption, by paying an overhead of $D \cdot \mathsf{poly}(\Delta)$ CONGEST rounds, where $\Delta$ is the maximum degree. Due to an inherent structural barrier, the generalization of the current framework to handling f corruptions, provably leads to an overhead of $O(\Delta D)^{\Theta(f)}$ rounds. This can also be shown to be tight for the class of store-and-forward algorithms1.1In which nodes can only propagate messages as atomic units, without the ability to mix multiple messages together.Secure Computation & Universal Optimality. We present an improved framework for secure computation which bypasses the current exponential in f barrier. For every graph $G=(V, E)$ with vertex-connectivity $\widetilde{\Omega}(f)$, our simulation provides a round overhead of $\mathsf{poly}(\Delta) \cdot \widehat{O}(\mathbf{S Q}(G))$.2The graph measure $\mathbf{S Q}(G)$ (Shortcut Quality) captures the universal optimal complexity of many network optimization tasks in the (non-secure) CONGEST model, as demonstrated in a recent breakthrough result of [Haeupler, Wajc and Zuzic, STOC 2021]. We are hopeful that the extended graph-theoretic machinery provided in this paper will find further applications in secure computation and beyond.2The notation $\widehat{O}(\cdot)$ hides $2^{O(\sqrt{\log n})}$ factors.

In their seminal PODC 1991 paper, Ostrovsky and Yung introduced the study of distributed computation in the presence of mobile adversaries which can dynamically appear throughout the network, analogous to a spread of a virus. Over the years, this setting has been studied mostly under the assumption that the communication graph is fully-connected. Resilient CONGEST algorithms for general graphs, on the other hand, are currently known only for the classical static setting, i.e., where the set of corrupted edges (or nodes) is fixed throughout the entire computation.

For an n-vertex m-edge digraph G, a D-shortcut is a small set H of directed edges taken from the transitive closure of G, satisfying that the diameter of G ∪ H is at most D. In a sequence of works [Kogan and Parter, SODA 2022 & ICALP 2022] provided shortcut algorithms with improved diameter vs. size tradeoffs. In this paper, we present faster and unified shortcut algorithms for general digraphs. These algorithms also yield improved tradeoffs for the family of bounded-width DAGs. We show:

The restoration lemma by Afek et al. [ 3 ] proves that, in an undirected unweighted graph, any replacement shortest path avoiding a failing edge can be expressed as the concatenation of two original shortest paths. However, the lemma is tiebreaking-sensitive : if one selects a particular canonical shortest path for each node pair, it is no longer guaranteed that one can build replacement paths by concatenating two selected shortest paths. They left as an open problem whether a method of shortest path tiebreaking with this desirable property is generally possible. We settle this question affirmatively with the first general construction of restorable tiebreaking schemes . We then show applications to various problems in fault-tolerant network design. These include a faster algorithm for subset replacement paths, more efficient fault-tolerant (exact) distance labeling schemes, fault-tolerant subset distance preservers and + 4 additive spanners with improved sparsity, and fast distributed algorithms that construct these objects. For example, an almost immediate corollary of our restorable tiebreaking scheme is the first nontrivial distributed construction of sparse fault-tolerant distance preservers resilient to three faults.

Theoretical study of optimization problems in wireless communication often deals with tasks that concern a single point. For example, the power control problem requires computing a power assignment guaranteeing that each transmitting station s i is successfully received at a single receiver point r i . This paper aims at addressing communication applications that require handling two-dimensional tasks (e.g., guaranteeing successful transmission in entire regions rather than at specific points). The natural approach to two-dimensional optimization tasks is to discretize the optimization domain, e.g., by sampling points within the domain. The straightforward implementation of the discretization approach, however, might incur high time and memory requirements, and moreover, it cannot guarantee exact solutions. The alternative proposed and explored in this paper is based on establishing the minimum principle 1 for the signal to interference and noise ratio (SINR) function with free space path loss (i.e., when the signal decays in proportion to the square of the distance between the transmitter and receiver). Essentially, the minimum principle allows us to reduce the dimension of the optimization domain without losing anything in the accuracy or quality of the solution. More specifically, when the two-dimensional optimization domain is bounded and free from any interfering station, the minimum principle implies that it is sufficient to optimize the SINR function over the boundary of the domain, as the “hardest” points to be satisfied reside on the boundary and not in the interior. We then utilize the minimum principle as the basis for an improved discretization technique for solving two-dimensional problems in the SINR model. This approach is shown to be useful for handling optimization problems over two dimensions (e.g., power control, energy minimization); in providing tight bounds on the number of null cells in the reception map; and in approximating geometric and topological properties of the wireless reception map (e.g., maximum inscribed sphere). The minimum principle, as well as the interplay between continuous and discrete analysis presented in this paper, are expected to pave the way to future study of algorithmic SINR in higher dimensions.

Hopsets and spanners are fundamental graph structures, playing a key role in shortest path computation, distributed communication, and more. A (near-exact) hopset for a given graph G is a (small) subset of weighted edges H that when added to the graph G reduces the number of hops (edges) of near-exact shortest paths. Spanners and distance preservers, on the other hand, ask for removing many edges from the graph while approximately preserving shortest path distances.We provide a general reduction scheme from graph hopsets to the known metric compression schemes of spanners, emulators and distance preservers. Consequently, we get new and improved upper bound constructions for the latter, as well as, new lower bound results for hopsets. Our main results include:•For n-vertex directed weighted graphs, one can provide $(1+\epsilon)$-approximate distance preservers1for p pairs in $V\times V$ with $O_{\epsilon}(n\cdot p^{2/5}+(np)^{2/3})$ edges. For $p\geq n^{5/4}$, this matches the state-of-the art bounds for reachability preservers by [Abboud and Bodwin, SODA 2018] and the lower bound for exact-distance preservers by [Bodwin, SODA 2016].•For n-vertex undirected weighted graphs, one can provide $(1+\epsilon)$ distance preserves with $\overline{O}_{\epsilon}(n^{1+o(1)}+p\cdot n^{o(1)})$ edges. So far, such bounds could be obtained only for unweighted graphs. Consequently, we also get improved sourcewise spanners [Roditty, Thorup and Zwick, ICALP 2005] and spanners with slack [Chan, Dinitz and Gupta, ESA 2006].•Exact hopsets of linear size admit a worst-case hopbound of $\beta=\Omega(n^{1/3})$. This holds even for undirected weighted graphs, improving upon the $\Omega(n^{1/6})$ lower bound by [Huang and Pettie, SIAM J. Discret. Math 2021]. Interestingly this matches the recent diameter bound achieved for linear directed shortcuts.1I.e., subgraphs that preserve the pairwise distances up to a multiplicative stretch of (1+$\epsilon$).More conceptually, our work makes a significant progress on the tantalizing open problem concerning the formal connection between hopsets and spanners, e.g., as posed by Elkin and Neiman [Bull. EATCS 2020].

Following the immense recent advances in distributed networks, the explosive growth of the Internet, and our increased dependency on these infrastructures, guaranteeing the uninterrupted operation of communication networks has become a major objective in network algorithms. The modern instantiations of distributed networks, such as the Bitcoin network and cloud computing, introduce new security challenges that deserve urgent attention in both theory and practice.

For an n-vertex digraph G = (V, E), a shortcut set is a (small) subset of edges H taken from the transitive closure of G that, when added to G guarantees that the diameter of G ∪ H is small. Shortcut sets, introduced by Thorup in 1993, have a wide range of applications in algorithm design, especially in the context of parallel, distributed and dynamic computation on directed graphs. A folklore result in this context shows that every n-vertex digraph admits a shortcut set of linear size (i.e., of O(n) edges) that reduces the diameter to1 . Despite extensive research over the years, the question of whether one can reduce the diameter to with Õ(n) shortcut edges has been left open. We provide the first improved diameter-sparsity tradeoff for this problem, breaking the diameter barrier. Specifically, we show an O(nω)-time randomized algorithm2 for computing a linear shortcut set that reduces the diameter of the digraph to Õ(n1/3). This narrows the gap w.r.t the current diameter lower bound of Ω(n1/6) by [Huang and Pettie, SWAT'18]. Moreover, we show that a diameter of O(n1/2) can in fact be achieved with a sublinear number of O(n3/4) shortcut edges. Formally, letting S(n, D) be the bound on the size of the shortcut set required in order to reduce the diameter of any n-vertex digraph to at most D, our algorithms yield: We also extend our algorithms to provide improved (β, ∊) hopsets for n-vertex weighted directed graphs.

We (nearly) settle the time complexity for computing vertex fault-tolerant (VFT) spanners with optimal sparsity (up to polylogarithmic factors). VFT spanners are sparse subgraphs that preserve distance information, up to a small multiplicative stretch, in the presence of vertex failures. These structures were introduced by [Chechik et al., STOC 2009] and have received a lot of attention since then.

We introduce new data structures for answering connectivity queries in graphs subject to batched vertex failures. A deterministic structure processes a batch of $d\leq d_{\star}$ failed vertices in $\tilde{O}(d^3)$ time and thereafter answers connectivity queries in $O(d)$ time. It occupies space $O(d_{\star} m\log n)$. We develop a randomized Monte Carlo version of our data structure with update time $\tilde{O}(d^2)$, query time $O(d)$, and space $\tilde{O}(m)$ for any failure bound $d\le n$. This is the first connectivity oracle for general graphs that can efficiently deal with an unbounded number of vertex failures. We also develop a more efficient Monte Carlo edge-failure connectivity oracle. Using space $O(n\log^2 n)$, $d$ edge failures are processed in $O(d\log d\log\log n)$ time and thereafter, connectivity queries are answered in $O(\log\log n)$ time, which are correct w.h.p. Our data structures are based on a new decomposition theorem for an undirected graph $G=(V,E)$, which is of independent interest. It states that for any terminal set $U\subseteq V$ we can remove a set $B$ of $|U|/(s-2)$ vertices such that the remaining graph contains a Steiner forest for $U-B$ with maximum degree $s$.

In this paper we present succinct labeling schemes for supporting connectivity queries under vertex faults. For a given $n$-vertex graph $G$, an $f$-VFT (resp., EFT) connectivity labeling scheme is a distributed data structure that assigns each of the graph edges and vertices a short label, such that given the labels of a vertex pair $u$ and $v$, and the labels of at most $f$ failing vertices (resp., edges) $F$, one can determine if $u$ and $v$ are connected in $G \setminus F$. The primary complexity measure is the length of the individual labels. Since their introduction by [Courcelle, Twigg, STACS '07], FT labeling schemes have been devised only for a limited collection of graph families. A recent work [Dory and Parter, PODC 2021] provided EFT labeling schemes for general graphs under edge failures, leaving the vertex failure case fairly open. We provide the first sublinear $f$-VFT labeling schemes for $f \geq 2$ for any $n$-vertex graph. Our key result is $2$-VFT connectivity labels with $O(\log^3 n)$ bits. Our constructions are based on analyzing the structure of dual failure replacement paths on top of the well-known heavy-light tree decomposition technique of [Sleator and Tarjan, STOC 1981]. We also provide $f$-VFT labels with sub-linear length (in $|V|$) for any $f=o(\log\log n)$, that are based on a reduction to the existing EFT labels.

We present improved deterministic algorithms for approximating shortest paths in the Congested Clique model of distributed computing. We obtain poly(log log n )-round algorithms for the following problems in unweighted undirected n -vertex graphs: ( 1 + ϵ )-approximation of multi-source shortest paths (MSSP) from O (√ n ) sources. (2 + ϵ )-approximation of all pairs shortest paths (APSP). (1 + ϵ , β)-approximation of APSP where β = O (log log n / ϵ ) log log n . These bounds improve exponentially over the state-of-the-art poly-logarithmic bounds due to [Censor-Hillel et al., PODC19]. It also provides the first nearly-additive bounds for the APSP problem in sub-polynomial time. Our approach is based on distinguishing between short and long distances based on some distance threshold t = O ( β / ϵ ) where β = O (log log n / ϵ ) log log n . Handling the long distances is done by devising a new algorithm for computing a sparse (1 + ϵ , β ) emulator with O ( n log log n ) edges. For the short distances, we provide distance-sensitive variants for the distance tool-kit of [Censor-Hillel et al., PODC19]. By exploiting the fact that this tool-kit should be applied only on local balls of radius t , their round complexities get improved from poly (log n ) to poly (log t ). Finally, our deterministic solutions for these problems are based on a derandomization scheme of a novel variant of the hitting set problem, which might be of independent interest.

The restoration lemma by Afek, Bremler-Barr, Kaplan, Cohen, and Merritt [Dist. Comp. '02] proves that, in an undirected unweighted graph, any replacement shortest path avoiding a failing edge can be expressed as the concatenation of two original shortest paths. However, the lemma is tiebreaking-sensitive: if one selects a particular canonical shortest path for each node pair, it is no longer guaranteed that one can build replacement paths by concatenating two selected shortest paths. They left as an open problem whether a method of shortest path tiebreaking with this desirable property is generally possible.

We present a deterministic O(log log log n)-round low-space Massively Parallel Computation (MPC) algorithm for the classical problem of (Δ+1)-coloring on n-vertex graphs. In this model, every machine has sublinear local space of size n^φ for any arbitrary constant φ \in (0,1). Our algorithm works under the relaxed setting where each machine is allowed to perform exponential local computations, while respecting the n^φ space and bandwidth limitations.

In this paper, we study the power and limitations of component-stable algorithms in the low-space model of Massively Parallel Computation (MPC). Recently Ghaffari, Kuhn and Uitto (FOCS 2019) introduced the class of component-stable low-space MPC algorithms, which are, informally, defined as algorithms for which the outputs reported by the nodes in different connected components are required to be independent. This very natural notion was introduced to capture most (if not all) of the known efficient MPC algorithms to date, and it was the first general class of MPC algorithms for which one can show non-trivial conditional lower bounds. In this paper we enhance the framework of component-stable algorithms and investigate its effect on the complexity of randomized and deterministic low-space MPC. Our key contributions include: 1) We revise and formalize the lifting approach of Ghaffari, Kuhn and Uitto. This requires a very delicate amendment of the notion of component stability, which allows us to fill in gaps in the earlier arguments. 2) We also extend the framework to obtain conditional lower bounds for deterministic algorithms and fine-grained lower bounds that depend on the maximum degree Δ. 3) We demonstrate a collection of natural graph problems for which non-component-stable algorithms break the conditional lower bound obtained for component-stable algorithms. This implies that, for both deterministic and randomized algorithms, component-stable algorithms are conditionally weaker than the non-component-stable ones.

Low congestion shortcuts, introduced by Ghaffari and Haeupler (SODA 2016), provide a unified framework for global optimization problems in the CONGEST model of distributed computing. Roughly speaking, for a given graph G and a collection of vertex-disjoint connected subsets S1,…,Sℓ ⊆V(G), (c,d) low-congestion shortcuts augment each subgraph G[Si] with a subgraph Hi ⊆G such that: (i) each edge appears on at most c subgraphs (congestion bound), and (ii) the diameter of each subgraph G[Si] ∪ Hi is bounded by d (dilation bound). It is desirable to compute shortcuts of small congestion and dilation as these quantities capture the round complexity of many global optimization problems in the CONGEST model. For n-vertex graphs with constant diameter D=O(1), Elkin (STOC 2004) presented an (implicit) shortcuts lower bound with1 c + d + Ωe (n (D-2)/(2D-2)). A nearly matching upper bound, however, was only recently obtained for D ∈ {3,4} by Kitamura et al. (DISC 2019).

In this article, we provide a unified and simplified approach to derandomize central results in the area of fault-tolerant graph algorithms. Given a graph G, a vertex pair (s, t) ∊ V(G) × V(G), and a set of edge faults F ⊆ E(G), a replacement path P(s, t, F) is an s-t shortest path in G \ F. For integer parameters L, f, a replacement path covering (RPC) is a collection of subgraphs of G, denoted by ∊L,f = {G1, …, Gr}, such that for every set F of at most f faults (i.e., |F| ≤ f) and every replacement path P(s, t, F) of at most L edges, there exists a subgraph Gi ∊ ∊L,f that contains all the edges of P and does not contain any of the edges of F. The covering value of the RPC GL,f is then defined to be the number of subgraphs in ∊L,f. In the randomized setting, it is easy to build an (L, f)-RPC with covering value of O(max{L, f}min{L,f} ·min{L, f}· log n), but to this date, there is no efficient deterministic algorithm with matching bounds. As noted recently by Alon, Chechik, and Cohen (ICALP 2019) this poses the key barrier for derandomizing known constructions of distance sensitivity oracles and fault-tolerant spanners. We show the following: There exist efficient deterministic constructions of (L, f)-RPCs whose covering values almost match the randomized ones, for a wide range of parameters. Our time and value bounds improve considerably over the previous construction of Parter (DISC 2019). Our algorithms are based on the introduction of a novel notion of hash families that we call Hit and Miss hash families. We then show how to construct these hash families from (algebraic) error correcting codes such as Reed-Solomon codes and Algebraic-Geometric codes. For every L, f, and n, there exists an n-vertex graph G whose (L, f)-RPC covering value is Ω(Lf). This lower bound is obtained by exploiting connections to the problem of designing sparse fault-tolerant BFS structures. An applications of our above deterministic constructions is the derandomization of the algebraic construction of the distance sensitivity oracle by Weimann and Yuster (FOCS 2010). The preprocessing and query time of our deterministic algorithm nearly match the randomized bounds. This resolves the open problem of Alon, Chechik and Cohen (ICALP 2019). Additionally, we show a derandomization of the randomized construction of vertex fault-tolerant spanners by Dinitz and Krauthgamer (PODC 2011) and Braunschvig et al. (Theor. Comput. Sci., 2015). The time complexity and the size bounds of the output spanners nearly match the randomized counterparts.

We consider the corner-stone broadcast task with an adaptive adversary that controls a fixed number of $t$ edges in the input communication graph. In this model, the adversary sees the entire communication in the network and the random coins of the nodes, while maliciously manipulating the messages sent through a set of $t$ edges (unknown to the nodes). Since the influential work of [Pease, Shostak and Lamport, JACM'80], broadcast algorithms against plentiful adversarial models have been studied in both theory and practice for over more than four decades. Despite this extensive research, there is no round efficient broadcast algorithm for general graphs in the CONGEST model of distributed computing. We provide the first round-efficient broadcast algorithms against adaptive edge adversaries. Our two key results for $n$-node graphs of diameter $D$ are as follows: 1. For $t=1$, there is a deterministic algorithm that solves the problem within $\widetilde{O}(D^2)$ rounds, provided that the graph is 3 edge-connected. This round complexity beats the natural barrier of $O(D^3)$ rounds, the existential lower bound on the maximal length of $3$ edge-disjoint paths between a given pair of nodes in $G$. This algorithm can be extended to a $\widetilde{O}(D^{O(t)})$-round algorithm against $t$ adversarial edges in $(2t+1)$ edge-connected graphs. 2. For expander graphs with minimum degree of $Ω(t^2\log n)$, there is an improved broadcast algorithm with $O(t \log ^2 n)$ rounds against $t$ adversarial edges. This algorithm exploits the connectivity and conductance properties of G-subgraphs obtained by employing the Karger's edge sampling technique. Our algorithms mark a new connection between the areas of fault-tolerant network design and reliable distributed communication.

We consider the adversarial CONGEST model of distributed computing in which a fixed number of edges (or nodes) in the graph are controlled by a computationally unbounded adversary that corrupts the computation by sending malicious messages over these (a-priori unknown) controlled edges. As in the standard CONGEST model, communication is synchronous, where per round each processor can send O(log n) bits to each of its neighbors. This paper is concerned with distributed algorithms that are both time efficient (in terms of the number of rounds), as well as, robust against a fixed number of adversarial edges. Unfortunately, the existing algorithms in this setting usually assume that the communication graph is complete (n-clique), and very little is known for graphs with arbitrary topologies. We fill in this gap by extending the methodology of [Parter and Yogev, SODA 2019] and provide a compiler that simulates any CONGEST algorithm 𝒜 (in the reliable setting) into an equivalent algorithm 𝒜' in the adversarial CONGEST model. Specifically, we show the following for every (2f+1) edge-connected graph of diameter D: - For f = 1, there is a general compiler against a single adversarial edge with a compilation overhead of Ô(D³) rounds. This improves upon the Ô(D⁵) round overhead of [Parter and Yogev, SODA 2019] and omits their assumption regarding a fault-free preprocessing phase. - For any constant f, there is a general compiler against f adversarial edges with a compilation overhead of Ô(D^{O(f)}) rounds. The prior compilers of [Parter and Yogev, SODA 2019] were limited to a single adversarial edge. Our compilers are based on a new notion of fault-tolerant cycle covers. The computation of these cycles in the adversarial CONGEST model constitutes the key technical contribution of the paper.

We settle the complexity of the $(\Delta+1)$-coloring and $(\Delta+1)$-list coloring problems in the \sf CONGESTED CLIQUE model by presenting a simple deterministic algorithm for both problems running in a constant number of rounds. This matches the complexity of the recent breakthrough randomized constant-round $(\Delta+1)$-list coloring algorithm due to Chang et al. [Proceedings of the 38th ACM Symposium on Principles of Distributed Computing, 2019] and significantly improves upon the state-of-the-art $O(\log \Delta)$-round deterministic $(\Delta+1)$-coloring bound of Parter [Proceedings of the 45th Annual International Colloquium on Automata, Languages and Programming]. A remarkable property of our algorithm is its simplicity. Whereas the state-of-the-art randomized algorithms for this problem are based on the quite involved local coloring algorithm of Chang, Li, and Pettie [Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018], our algorithm can be described in just a few lines. At a high level, it applies a careful derandomization of a recursive procedure which partitions the nodes and their respective palettes into separate bins. We show that after $O(1)$ recursion steps, the remaining uncolored subgraph within each bin has linear size and thus can be solved locally by collecting it to a single node. This algorithm can also be implemented in the massively parallel computation (\sf MPC) model provided that each machine has linear (in ${\mathfrak{n}}$, the number of nodes in the input graph) space. We also show an extension of our algorithm to the \sf MPC regime, in which machines have sublinear space: we present the first deterministic $(\Delta+1)$-list coloring algorithm designed for sublinear-space \sf MPC, which runs in $O(\log \Delta + \log \log \mathfrak{n})$ rounds.

Fault tolerant distance preservers are sparse subgraphs that preserve distances between given pairs of nodes under edge or vertex failures. In this paper, we present the first non-trivial constructions of subset distance preservers, which preserve all distances among a subset of nodes S, that can handle either an edge or a vertex fault. - For an n-vertex undirected weighted graph or weighted DAG G = (V,E) and S ⊆ V, we present a construction of a subset preserver with Õ(|S|n) edges that is resilient to a single fault. In the single pair case (|S| = 2), the bound improves to O(n). We further provide a nearly-matching lower bound of Ω(|S|n) in either setting, and we show that the same lower bound holds conditionally even if attention is restricted to unweighted graphs. - For an n-vertex directed unweighted graph G = (V,E) and r ∈ V, S ⊆ V, we present a construction of a preserver of distances in {r} × S with Õ(n^{4/3} |S|^{5/6}) edges that is resilient to a single fault. In the case |S| = 1 the bound improves to O(n^{4/3}), and for this case we provide another matching conditional lower bound. - For an n-vertex directed weighted graph G = (V, E) and r ∈ V, S ⊆ V, we present a construction of a preserver of distances in {r} × S with Õ(n^{3/2} |S|^{3/4}) edges that is resilient to a single vertex fault. (It was proved in [Greg Bodwin et al., 2017] that the bound improves to O(n^{3/2}) when |S| = 1, and that this is conditionally tight.)

Edge connectivity of a graph is one of the most fundamental graph-theoretic concepts. The celebrated tree packing theorem of Tutte and Nash-Williams from 1961 states that every k-edge connected graph G contains a collection 𝒯 of ⌊k/2⌋ edge-disjoint spanning trees, that we refer to as a tree packing; the diameter of the tree packing 𝒯 is the largest diameter of any tree in 𝒯. A desirable property of a tree packing for leveraging the high connectivity of a graph in distributed communication networks, is that its diameter is low. Yet, despite extensive research in this area, it is still unclear how to compute a tree packing of a low-diameter graph G, whose diameter is sublinear in |V(G)|, or, alternatively, how to show that such a packing does not exist. In this paper, we provide first non-trivial upper and lower bounds on the diameter of tree packing. We start by showing that, for every k-edge connected n-vertex graph G of diameter D, there is a tree packing 𝒯 containing Ω(k) trees, of diameter O((101k log n)^D), with edge-congestion at most 2. Karger’s edge sampling technique demonstrates that, if G is a k-edge connected graph, and G[p] is a subgraph of G obtained by sampling each edge of G independently with probability p = Θ(log n/k), then with high probability G[p] is connected. We extend this result to show that the diameter of G[p] is bounded by O(k^(D(D+1)/2)) with high probability. This immediately gives a tree packing of Ω(k/log n) edge-disjoint trees of diameter at most O(k^(D(D+1)/2)). We also show that these two results are nearly tight for graphs with a small diameter: we show that there are k-edge connected graphs of diameter 2D, such that any packing of k/α trees with edge-congestion η contains at least one tree of diameter Ω((k/(2α η D))^D), for any k,α and η. Additionally, we show that if, for every pair u,v of vertices of a given graph G, there is a collection of k edge-disjoint paths connecting u to v, of length at most D each, then we can efficiently compute a tree packing of size k, diameter O(D log n), and edge-congestion O(log n). Finally, we provide several applications of low-diameter tree packing in the distributed settings of network optimization and secure computation.

We study input compression in a biologically inspired model of neural computation. We demonstrate that a network consisting of a random projection step (implemented via random synaptic connectivity) followed by a sparsification step (implemented via winner-take-all competition) can reduce well-separated high-dimensional input vectors to well-separated low-dimensional vectors. By augmenting our network with a third module, we can efficiently map each input (along with any small perturbations of the input) to a unique representative neuron, solving a neural clustering problem. Both the size of our network and its processing time, i.e., the time it takes the network to compute the compressed output given a presented input, are independent of the (potentially large) dimension of the input patterns and depend only on the number of distinct inputs that the network must encode and the pairwise relative Hamming distance between these inputs. The first two steps of our construction mirror known biological networks, for example, in the fruit fly olfactory system [Caron et al., 2013; Lin et al., 2014; Dasgupta et al., 2017]. Our analysis helps provide a theoretical understanding of these networks and lay a foundation for how random compression and input memorization may be implemented in biological neural networks. Technically, a contribution in our network design is the implementation of a short-term memory. Our network can be given a desired memory time t_m as an input parameter and satisfies the following with high probability: any pattern presented several times within a time window of t_m rounds will be mapped to a single representative output neuron. However, a pattern not presented for c⋅t_m rounds for some constant c>1 will be "forgotten", and its representative output neuron will be released, to accommodate newly introduced patterns.

Biological neural computation is inherently asynchronous due to large variations in neuronal spike timing and transmission delays. So-far, most theoretical work on neural networks assumes the synchronous setting where neurons fire simultaneously in discrete rounds. In this work we aim at understanding the barriers of asynchronous neural computation from an algorithmic perspective. We consider an extension of the widely studied model of synchronized spiking neurons [Maass, Neural Networks 97] to the asynchronous setting by taking into account edge and node delays. - Edge Delays: We define an asynchronous model for spiking neurons in which the latency values (i.e., transmission delays) of non self-loop edges vary adversarially over time. This extends the recent work of [Hitron and Parter, ESA'19] in which the latency values are restricted to be fixed over time. Our first contribution is an impossibility result that implies that the assumption that self-loop edges have no delays (as assumed in Hitron and Parter) is indeed necessary. Interestingly, in real biological networks self-loop edges (a.k.a. autapse) are indeed free of delays, and the latter has been noted by neuroscientists to be crucial for network synchronization. To capture the computational challenges in this setting, we first consider the implementation of a single NOT gate. This simple function already captures the fundamental difficulties in the asynchronous setting. Our key technical results are space and time upper and lower bounds for the NOT function, our time bounds are tight. In the spirit of the distributed synchronizers [Awerbuch and Peleg, FOCS'90] and following [Hitron and Parter, ESA'19], we then provide a general synchronizer machinery. Our construction is very modular and it is based on efficient circuit implementation of threshold gates. The complexity of our scheme is measured by the overhead in the number of neurons and the computation time, both are shown to be polynomial in the largest latency value, and the largest incoming degree Δ of the original network. - Node Delays: We introduce the study of asynchronous communication due to variations in the response rates of the neurons in the network. In real brain networks, the round duration varies between different neurons in the network. Our key result is a simulation methodology that allows one to transform the above mentioned synchronized solution under edge delays into a synchronized under node delays while incurring a small overhead w.r.t space and time.

We settle the complexity of the (Δ + 1)-coloring and (Δ + 1)-list coloring problems in the CONGESTED CLIQUE model by presenting a simple deterministic algorithm for both problems running in a constant number of rounds. This matches the complexity of the recent breakthrough randomized constant-round (Δ + 1)-list coloring algorithm due to Chang et al. (PODC'19), and significantly improves upon the state-of-the-art O(log Δ)-round deterministic (Δ + 1)-coloring bound of Parter (ICALP'18).

We present improved deterministic algorithms for approximating shortest paths in the Congested Cliqe model of distributed computing. We obtain poly(log log n)-round algorithms for the following problems in unweighted undirected n-vertex graphs:

An f (d)-spanner of an unweighted n-vertex graph G = (V, E) is a subgraph H satisfying that distH(u, v) is at most f (distG (u, v)) for every u, v ϵ V. A simple girth argument implies that any f (d)-spanner with O(n1+1/k) edges must satisfy that f (d) / d = Ω(⌈k/d⌉). A matching upper bound (even up to constants) for super-constant values of d is currently known only for d = Ω((logk)log k) as given by the well known (1 + ε, β) spanners of Elkin and Peleg, and its recent improvements by [Elkin-Neiman, SODA’17], and [Abboud-Bodwin-Pettie, SODA’18]. We present new spanner constructions that achieve a nearly optimal stretch of O(⌈k/d⌉) for any distance value d ϵ [1, k1−o(1)] and d ≥ k1+o(1). We also show more optimized spanner constructions with nearly linear number of edges. Specifically, for every ε ϵ (0, 1), we show the construction of (3 + ε, β) spanners for β = Oε (klog(3+8/ε)) with Õε (n) edges. In addition, we consider the related graph concept of hopsets introduced by [Cohen, J. ACM ‘00]. Informally, an hopset H is a weighted edge set that, when added to the graph G, allows one to get a path from each node u to a node v with at most β hops (i.e., edges) and length at most α · distG (u, v). We present a new family of (α, β) hopsets with Õ(k · n1+1/k) edges and α · β = O(k). Turning to nearly linear-size hopsets, we show a construction of (3 + ε, β) hopset with Õε(n) edges and hop-bound of β = Oε ((log n)log(3+9/ε)), improving upon the state-of-the-art hop-bound of β = O(log log n)log log n.

We explore the power of interactive proofs with a distributed verifier. In this setting, the verifier consists of n nodes and a graph G that defines their communication pattern. The prover is a single entity that communicates with all nodes by short messages. The goal is to verify that the graph G belongs to some language in a small number of rounds, and with small communication bound, i.e., the proof size. This interactive model was introduced by Kol, Oshman and Saxena (PODC 2018) as a generalization of noninteractive distributed proofs. They demonstrated the power of interaction in this setting by constructing protocols for problems as Graph Symmetry and Graph Non-Isomorphism – both of which require proofs of Ω(n2)-bits without interaction. In this work, we provide a new general framework for distributed interactive proofs that allows one to translate standard interactive protocols (i.e., with a centralized verifier) to ones where the verifier is distributed with a proof size that depends on the computational complexity of the verification algorithm run by the centralized verifier. We show the following: Every (centralized) computation performed in time O(n) on a RAM can be translated into three-round distributed interactive protocol with O(log n) proof size. This implies that many graph problems for sparse graphs have succinct proofs (e.g., testing planarity). Every (centralized) computation implemented by either a small space or by uniform NC circuit can be translated into a distributed protocol with O(1) rounds and O(log n) bits proof size for the low space case and polylog(n) many rounds and proof size for NC. We show that for Graph Non-Isomorphism, one of the striking demonstrations of the power of interaction, there is a 4-round protocol with O(log n) proof size, improving upon the O(n log n) proof size of Kol et al. For many problems, we show how to reduce proof size below the seemingly natural barrier of log n. By employing our RAM compiler, we get a 5-round protocol with proof size O (log log n) for a family of problems including Fixed Automorphism, Clique and Leader Election (for the latter two problems we actually get O(1) proof size). Finally, we discuss how to make these proofs noninteractive arguments via random oracles. Our compilers capture many natural problems and demonstrate the difficulty in showing lower bounds in these regimes.

Massively Parallel Computation (MPC) is an emerging model which distills core aspects of distributed and parallel computation. It was developed as a tool to solve (typically graph) problems in systems where input is distributed over many machines with limited space. Recent work has focused on the regime in which machines have sublinear (in n, number of nodes in the input graph) space, with randomized algorithms presented for the fundamental problems of Maximal Matching and Maximal Independent Set. There are, however, no prior corresponding deterministic algorithms.

Fault tolerant distance preservers (spanners) are sparse subgraphs that preserve (approximate) distances between given pairs of vertices under edge or vertex failures. So-far, these structures have been studied mainly from a centralized viewpoint. Despite the fact fault tolerant preservers are mainly motivated by the error-prone nature of distributed networks, not much is known on the distributed computational aspects of these structures. In this paper, we present distributed algorithms for constructing fault tolerant distance preservers and $+2$ additive spanners that are resilient to at most \emph{two edge} faults. Prior to our work, the only non-trivial constructions known were for the \emph{single} fault and \emph{single source} setting by [Ghaffari and Parter SPAA'16]. Our key technical contribution is a distributed algorithm for computing distance preservers w.r.t. a subset $S$ of source vertices, resilient to two edge faults. The output structure contains a BFS tree $BFS(s,G \setminus \{e_1,e_2\})$ for every $s \in S$ and every $e_1,e_2 \in G$. The distributed construction of this structure is based on a delicate balance between the edge congestion (formed by running multiple BFS trees simultaneously) and the sparsity of the output subgraph. No sublinear-round algorithms for constructing these structures have been known before.

We present nearly optimal distributed algorithms for fundamental reachability problems in planar graphs. In the single-source reachability problem given is an n-vertex directed graph G = (V,E) and a source node s, it is required to determine the subset of nodes that are reachable from s in G. We present the first distributed reachability algorithm for planar graphs that runs in nearly optimal time of Õ(D) rounds, where D is the undirected diameter of the graph. This improves the complexity of Õ(D²) rounds implied by the recent work of [Li and Parter, STOC'19]. We also consider the more general reachability problem of identifying the strongly connected components (SCCs) of the graph. We present an Õ(D)-round algorithm that computes for each node in the graph an identifier of its strongly connected component in G. No non-trivial upper bound for this problem (even in general graphs) has been known before. Our algorithms are based on characterizing the structural interactions between balanced cycle separators. We show that the reachability relations between separator nodes can be compressed due to a Monge-like property of their directed shortest paths. The algorithmic results are obtained by combining this structural characterization with the recursive graph partitioning machinery of [Li and Parter, STOC'19].

This paper addresses the cornerstone family of local problems in distributed computing, and investigates the curious gap between randomized and deterministic solutions under bandwidth restrictions. Our main contribution is in providing tools for derandomizing solutions to local problems, when the n nodes can only send \(O(\log n)\) -bit messages in each round of communication. Our framework mostly follows by the derandomization approach of Luby (J Comput Syst Sci 47(2):250–286, 1993) combined with the power of all to all communication. Our key results are as follows: first, we show that in the congested clique model, which allows all-to-all communication, there is a deterministic maximal independent set algorithm that runs in \(O(\log ^2 {\varDelta })\) rounds, where \({\varDelta }\) is the maximum degree. When \({\varDelta }=O(n^{1/3})\) , the bound improves to \(O(\log {\varDelta })\) . In addition, we deterministically construct a \((2k-1)\) -spanner with \(O(kn^{1+1/k}\log n)\) edges in \(O(k \log n)\) rounds in the congested clique model.

We consider the task of measuring time with probabilistic threshold gates implemented by bio-inspired spiking neurons. In the model of spiking neural networks, network evolves in discrete rounds, where in each round, neurons fire in pulses in response to a sufficiently high membrane potential. This potential is induced by spikes from neighboring neurons that fired in the previous round, which can have either an excitatory or inhibitory effect. Discovering the underlying mechanisms by which the brain perceives the duration of time is one of the largest open enigma in computational neuro-science. To gain a better algorithmic understanding onto these processes, we introduce the neural timer problem. In this problem, one is given a time parameter t, an input neuron x, and an output neuron y. It is then required to design a minimum sized neural network (measured by the number of auxiliary neurons) in which every spike from x in a given round i, makes the output y fire for the subsequent t consecutive rounds. We first consider a deterministic implementation of a neural timer and show that Theta(log t) (deterministic) threshold gates are both sufficient and necessary. This raised the question of whether randomness can be leveraged to reduce the number of neurons. We answer this question in the affirmative by considering neural timers with spiking neurons where the neuron y is required to fire for t consecutive rounds with probability at least 1-delta, and should stop firing after at most 2t rounds with probability 1-delta for some input parameter delta in (0,1). Our key result is a construction of a neural timer with O(log log 1/delta) spiking neurons. Interestingly, this construction uses only one spiking neuron, while the remaining neurons can be deterministic threshold gates. We complement this construction with a matching lower bound of Omega(min{log log 1/delta, log t}) neurons. This provides the first separation between deterministic and randomized constructions in the setting of spiking neural networks. Finally, we demonstrate the usefulness of compressed counting networks for synchronizing neural networks. In the spirit of distributed synchronizers [Awerbuch-Peleg, FOCS'90], we provide a general transformation (or simulation) that can take any synchronized network solution and simulate it in an asynchronous setting (where edges have arbitrary response latencies) while incurring a small overhead w.r.t the number of neurons and computation time.

Short cycle decomposition is an edge partitioning of an unweighted graph into edge-disjoint short cycles, plus a small number of extra edges not in any cycle. This notion was introduced by Chu et al. [FOCS'18] as a fundamental tool for graph sparsification and sketching. Clearly, it is most desirable to have a fast algorithm for partitioning the edges into as short as possible cycles, while omitting few edges. The most naïve procedure for such decomposition runs in time O(m * n) and partitions the edges into O(log n)-length edge-disjoint cycles plus at most 2n edges. Chu et al. improved the running time considerably to m^{1+o(1)}, while increasing both the length of the cycles and the number of omitted edges by a factor of n^{o(1)}. Even more recently, Liu-Sachdeva-Yu [SODA'19] showed that for every constant delta in (0,1] there is an O(m * n^{delta})-time algorithm that provides, w.h.p., cycles of length O(log n)^{1/delta} and O(n) extra edges. In this paper, we significantly improve upon these bounds. We first show an m^{1+o(1)}-time deterministic algorithm for computing nearly optimal cycle decomposition, i.e., with cycle length O(log^2 n) and an extra subset of O(n log n) edges not in any cycle. This algorithm is based on a reduction to low-congestion cycle covers, introduced by the authors in [SODA'19]. We also provide a simple deterministic algorithm that computes edge-disjoint cycles of length 2^{1/epsilon} with n^{1+epsilon}* 2^{1/epsilon} extra edges, for every epsilon in (0,1]. Combining this with Liu-Sachdeva-Yu [SODA'19] gives a linear time randomized algorithm for computing cycles of length poly(log n) and O(n) extra edges, for every n-vertex graphs with n^{1+1/delta} edges for some constant delta. These decomposition algorithms lead to improvements in all the algorithmic applications of Chu et al. as well as to new distributed constructions.

A graph spanner is a fundamental graph structure that faithfully preserves the pairwise distances in the input graph up to a small multiplicative stretch. The common objective in the computation of spanners is to achieve the best-known existential size-stretch trade-off efficiently. Classical models and algorithmic analysis of graph spanners essentially assume that the algorithm can read the input graph, construct the desired spanner, and write the answer to the output tape. However, when considering massive graphs containing millions or even billions of nodes not only the input graph, but also the output spanner might be too large for a single processor to store. To tackle this challenge, we initiate the study of local computation algorithms (LCAs) for graph spanners in general graphs, where the algorithm should locally decide whether a given edge $(u,v) \in E$ belongs to the output spanner. Such LCAs give the user the `illusion' that a specific sparse spanner for the graph is maintained, without ever fully computing it. We present the following results: -For general $n$-vertex graphs and $r \in \{2,3\}$, there exists an LCA for $(2r-1)$-spanners with $\widetilde{O}(n^{1+1/r})$ edges and sublinear probe complexity of $\widetilde{O}(n^{1-1/2r})$. These size/stretch tradeoffs are best possible (up to polylogarithmic factors). -For every $k \geq 1$ and $n$-vertex graph with maximum degree $Δ$, there exists an LCA for $O(k^2)$ spanners with $\widetilde{O}(n^{1+1/k})$ edges, probe complexity of $\widetilde{O}(Δ^4 n^{2/3})$, and random seed of size $\mathrm{polylog}(n)$. This improves upon, and extends the work of [Lenzen-Levi, 2018]. We also complement our results by providing a polynomial lower bound on the probe complexity of LCAs for graph spanners that holds even for the simpler task of computing a sparse connected subgraph with $o(m)$ edges.

In this paper, we study secure distributed algorithms that are nearly optimal, with respect to running time, for the given input graph G. Roughly speaking, an algorithm is secure if the nodes learn only their final output while gaining no information on the input (or output) of other nodes.

A cycle cover of a bridgeless graph G is a collection of simple cycles in G such that each edge e appears on at least one cycle. The common objective in cycle cover computation is to minimize the total lengths of all cycles. Motivated by applications to distributed computation, we introduce the notion of low-congestion cycle covers, in which all cycles in the cycle collection are both short and nearly edge-disjoint. Formally, a (d, c)-cycle cover of a graph G is a collection of cycles in G in which each cycle is of length at most d and each edge participates in at least one cycle and at most c cycles. A-priori, it is not clear that cycle covers that enjoy both a small overlap and a short cycle length even exist, nor if it is possible to efficiently find them. Perhaps quite surprisingly, we prove the following: Every bridgeless graph of diameter D admits a (d, c)-cycle cover where d = Õ(D) and c = Õ(1). That is, the edges of G can be covered by cycles such that each cycle is of length at most Õ(D) and each edge participates in at most Õ(1) cycles. These parameters are existentially tight up to polylogarithmic terms. Furthermore, we show how to extend our result to achieve universally optimal cycle covers. Let Ce is the shortest cycle that covers e, and let OPT(G) = maxe∊G |Ce|. We show that every bridgeless graph admits a (d, c)-cycle cover where d = Õ(OPT(G)) and c = Õ(1). We demonstrate the usefulness of low congestion cycle covers in different settings of resilient computation. For instance, we consider a Byzantine fault model where in each round, the adversary chooses a single message and corrupt in an arbitrarily manner. We provide a compiler that turns any r-round distributed algorithm for a graph G with diameter D, into an equivalent fault tolerant algorithm with r·poly(D) rounds.

In the area of distributed graph algorithms a number of network's entities with local views solve some computational task by exchanging messages with their neighbors. Quite unfortunately, an inherent property of most existing distributed algorithms is that throughout the course of their execution, the nodes get to learn not only their own output but rather learn quite a lot on the inputs or outputs of many other entities. This leakage of information might be a major obstacle in settings where the output (or input) of network's individual is a private information (e.g., distributed networks of selfish agents, decentralized digital currency such as Bitcoin). While being quite an unfamiliar notion in the classical distributed setting, the notion of secure multi-party computation (MPC) is one of the main themes in the Cryptographic community. The existing secure MPC protocols do not quite fit the framework of classical distributed models in which only messages of bounded size are sent on graph edges in each round. In this paper, we introduce a new framework for secure distributed graph algorithms and provide the first general compiler that takes any “natural” non-secure distributed algorithm that runs in r rounds, and turns it into a secure algorithm that runs in Õ(r · D · poly(Δ)) rounds where Δ is the maximum degree in the graph and D is its diameter. A “natural” distributed algorithm is one where the local computation at each node can be performed in polynomial time. An interesting advantage of our approach is that it allows one to decouple between the price of locality and the price of security of a given graph function f. The security of the compiled algorithm is information-theoretic but holds only against a semi-honest adversary that controls a single node in the network. This compiler is made possible due to a new combinatorial structure called private neighborhood trees: a collection of n trees T(u1), …, T(un), one for each vertex ui ∊ V(G), such that each tree T(ui) spans the neighbors of ui without going through ui. Intuitively, each tree T(ui) allows all neighbors of ui to exchange a secret that is hidden from ui, which is the basic graph infrastructure of the compiler. In a (d, c)-private neighborhood trees each tree T(ui) has depth at most d and each edge e ∊ G appears in at most c different trees. We show a construction of private neighborhood trees with d = Õ(Δ · D) and c = Õ(D), both these bounds are existentially optimal.

We study parallel algorithms for the classical balls-into-bins problem, in which m balls acting in parallel as separate agents are placed into n bins. Algorithms operate in synchronous rounds, in each of which balls and bins exchange messages once. The goal is to minimize the maximal load over all bins using a small number of rounds and few messages. While the case of $m=n$ balls has been extensively studied, little is known about the heavily loaded case. In this work, we consider parallel algorithms for this somewhat neglected regime of $m\gg n$. The naive solution of allocating each ball to a bin chosen uniformly and independently at random results in maximal load $m/n+Θ(\sqrtm/n\cdot łog n )$ (for $m\geq n łog n$) with high probability (w.h.p.). In contrast, for the sequential setting Berenbrink et al (SIAM J. Comput 2006) showed that letting each ball join the least loaded bin of two randomly selected bins reduces the maximal load to $m/n+O(łogłog m)$ w.h.p. To date, no parallel variant of such a result is known. We present a simple parallel threshold algorithm that obtains a maximal load of $m/n+O(1)$ w.h.p. within $O(łogłog (m/n)+łog^* n)$ rounds. The algorithm is symmetric (balls and bins all "look the same"), and balls send $O(1)$ messages in expectation per round. The additive term of $O(łog^* n)$ in the complexity is known to be tight for such algorithms (Lenzen and Wattenhofer Distributed Computing 2016). We also prove that our analysis is tight, i.e., algorithms of the type we provide must run for $Ømega(\min\łogłog (m/n),n\ )$ rounds w.h.p. Finally, we give a simple asymmetric algorithm (i.e., balls are aware of a common labeling of the bins) that achieves a maximal load of $m/n + O(1)$ in a constant number of rounds w.h.p. Again, balls send only a single message per round, and bins receive $(1+o(1))m/n+O(łog n)$ messages w.h.p. This goes to show that, similar to the case of $m=n$, asymmetry allows for highly efficient solutions.

We develop a new approach for distributed distance computation in planar graphs that is based on a variant of the metric compression problem recently introduced by Abboud et al. [SODA’18]. In our variant of the Planar Graph Metric Compression Problem, one is given an n-vertex planar graph G=(V,E), a set of S ⊆ V source terminals lying on a single face, and a subset of target terminals T ⊆ V. The goal is to compactly encode the S× T distances.

We revisit classical connectivity problems in the {CONGEST} model of distributed computing. By using techniques from fault tolerant network design, we show improved constructions, some of which are even "local" (i.e., with O~(1) rounds) for problems that are closely related to hard global problems (i.e., with a lower bound of Omega(Diam+sqrt{n}) rounds). Distributed Minimum Cut: Nanongkai and Su presented a randomized algorithm for computing a (1+epsilon)-approximation of the minimum cut using O~(D +sqrt{n}) rounds where D is the diameter of the graph. For a sufficiently large minimum cut lambda=Omega(sqrt{n}), this is tight due to Das Sarma et al. [FOCS '11], Ghaffari and Kuhn [DISC '13]. - Small Cuts: A special setting that remains open is where the graph connectivity lambda is small (i.e., constant). The only lower bound for this case is Omega(D), with a matching bound known only for lambda <= 2 due to Pritchard and Thurimella [TALG '11]. Recently, Daga, Henzinger, Nanongkai and Saranurak [STOC '19] raised the open problem of computing the minimum cut in poly(D) rounds for any lambda=O(1). In this paper, we resolve this problem by presenting a surprisingly simple algorithm, that takes a completely different approach than the existing algorithms. Our algorithm has also the benefit that it computes all minimum cuts in the graph, and naturally extends to vertex cuts as well. At the heart of the algorithm is a graph sampling approach usually used in the context of fault tolerant (FT) design. - Deterministic Algorithms: While the existing distributed minimum cut algorithms are randomized, our algorithm can be made deterministic within the same round complexity. To obtain this, we introduce a novel definition of universal sets along with their efficient computation. This allows us to derandomize the FT graph sampling technique, which might be of independent interest. - Computation of all Edge Connectivities: We also consider the more general task of computing the edge connectivity of all the edges in the graph. In the output format, it is required that the endpoints u,v of every edge (u,v) learn the cardinality of the u-v cut in the graph. We provide the first sublinear algorithm for this problem for the case of constant connectivity values. Specifically, by using the recent notion of low-congestion cycle cover, combined with the sampling technique, we compute all edge connectivities in poly(D) * 2^{O(sqrt{log n log log n})} rounds. Sparse Certificates: For an n-vertex graph G and an integer lambda, a lambda-sparse certificate H is a subgraph H subseteq G with O(lambda n) edges which is lambda-connected iff G is lambda-connected. For D-diameter graphs, constructions of sparse certificates for lambda in {2,3} have been provided by Thurimella [J. Alg. '97] and Dori [PODC '18] respectively using O~(D) number of rounds. The problem of devising such certificates with o(D+sqrt{n}) rounds was left open by Dori [PODC '18] for any lambda >= 4. Using connections to fault tolerant spanners, we considerably improve the round complexity for any lambda in [1,n] and epsilon in (0,1), by showing a construction of (1-epsilon)lambda-sparse certificates with O(lambda n) edges using only O(1/epsilon^2 * log^{2+o(1)} n) rounds.

In this paper, we present improved algorithms for the (Delta+1) (vertex) coloring problem in the Congested Clique model of distributed computing. In this model, the input is a graph on n nodes, initially each node knows only its incident edges, and per round each two nodes can exchange O(log n) bits of information. Our key result is a randomized (Delta+1) vertex coloring algorithm that works in O(log log Delta * log^* Delta)-rounds. This is achieved by combining the recent breakthrough result of [Chang-Li-Pettie, STOC'18] in the {LOCAL} model and a degree reduction technique. We also get the following results with high probability: (1) (Delta+1)-coloring for Delta=O((n/log n)^{1-epsilon}) for any epsilon in (0,1), within O(log(1/epsilon)log^* Delta) rounds, and (2) (Delta+Delta^{1/2+o(1)})-coloring within O(log^* Delta) rounds. Turning to deterministic algorithms, we show a (Delta+1)-coloring algorithm that works in O(log Delta) rounds. Our new bounds provide exponential improvements over the state of the art.

A k-spanner of a graph G is a sparse subgraph H whose shortest path distances match those of G up to a multiplicative error k. In this paper we study spanners that are resistant to faults. A subgraph H ⊆ G is an f vertex fault tolerant (VFT) k-spanner if H \ F is a k-spanner of G \ F for any small set F of f vertices that might “fail.” One of the main questions in the area is: what is the minimum size of an f fault tolerant k-spanner that holds for all n node graphs (as a function of f, k and n)? This question was first studied in the context of geometric graphs [Levcopoulos et al. STOC ’98, Czumaj and Zhao SoCG ’03] and has more recently been considered in general undirected graphs [Chechik et al. STOC ’09, Dinitz and Krauthgamer PODC ’11]. In this paper, we settle the question of the optimal size of a VFT spanner, in the setting where the stretch factor k is fixed. Specifically, we prove that every (undirected, possibly weighted) n-node graph G has a (2k – 1)-spanner resilient to f vertex faults with Ok (f1–1/kn1+1/k) edges, and this is fully optimal (unless the famous Erdös Girth Conjecture is false). Our lower bound even generalizes to imply that no data structure capable of approximating distG\F (s, t) similarly can beat the space usage of our spanner in the worst case. To the best of our knowledge, this is the first instance in fault tolerant network design in which introducing fault tolerance to the structure increases the size of the (non-FT) structure by a sublinear factor in f. Another advantage of this result is that our spanners are constructed by a very natural and simple greedy algorithm, which is the obvious extension of the standard greedy algorithm used to build spanners in the non-faulty setting. We also consider the edge fault tolerant (EFT) model, defined analogously with edge failures rather than vertex failures. We show that the same spanner upper bound applies in this setting. Our data structure lower bound extends to the case k = 2 (and hence we close the EFT problem for 3-approximations), but it falls to D(f 1/2-1/(2k) · n1+1/k) for k > 3. We leave it as an open problem to close this gap.

This paper introduces an extended notion of expansion suitable for radio networks. A graph G=(V,E) is said to be an (α_w, β_w) -\em wireless expander if for every subset S \subseteq V s.t. |S|łeq α_w \cdot |V| , there exists a subset S'\subseteq S s.t. there are at least β_w \cdot |S| vertices in V\backslash S that are adjacent in G to exactly one vertex in S' . The main question we ask is the following: to what extent are ordinary expanders also good wireless expanders? We answer this question in a nearly tight manner. On the positive side, we show that any (α, β)-expander with maximum degree Δ and β\geq 1/Δ$ is also a $(α_w, β_w)$ wireless expander with α_w \ge α$ and β_w = Ømega(β / łog (2 \cdot \min\Δ / β, Δ \cdot β\ ))$. Thus the wireless expansion can be smaller than the ordinary expansion by at most a factor that is logarithmic in \min\Δ / β, Δ \cdot β\ , which, in turn, depends on the average degree rather than the maximum degree of the graph. In particular, for low arboricity graphs (such as planar graphs), the wireless expansion matches the ordinary expansion up to a constant factor. We complement this positive result by presenting an explicit construction of a "bad'' (α, β) -expander for which the wireless expansion is β_w = O(β / łog (2 \cdot \min\Δ / β, Δ \cdot β\ ) . We also analyze the theoretical properties of wireless expanders and their connection to unique neighbor expanders, and then demonstrate their applicability: Our results (both the positive and the negative) yield improved bounds for the spokesmen election problem that was introduced in the seminal paper of Chlamtac and Weinstein from 1991 to devise efficient broadcasting for multihop radio networks. Our negative result yields a significantly simpler proof than that from the seminal paper of Kushilevitz and Mansour from 1998 for a lower bound on the broadcast time in radio networks.

Real life graphs and networks are prone to failure of nodes (vertices) and links (edges). In particular, for a pair of nodes s and t and a failing edge e in an n-vertex unweighted graph G=(V(G),E(G)), the replacement path pi_{G-e}(s,t) is a shortest s-t path that avoids e. In this paper we present several efficient constructions that, for every (s,t) \in S x T, where S, T \subseteq V(G), and every e \in E(G), maintain the collection of all pi_{G-e}(s,t), either implicitly (i.e., through compact data structures a.k.a. distance sensitivity oracles (DSO)), or explicitly (i.e., through sparse subgraphs a.k.a. fault-tolerant preservers (FTP)). More precisely, we provide the following results: (1) DSO: For every S,T \subseteq V(G), we construct a DSO for maintaining S x T distances under single edge (or vertex) faults. This DSO has size tilde{O}(n\sqrt{|S||T|}) and query time of O(\sqrt{|S||T|}). At the expense of having quasi-polynomial query time, the size of the oracle can be improved to tilde{O}(n|S|+|T|\sqrt{|S|n}), which is optimal for |T| = Omega(sqrt{n|S|}). When |T| = Omega(n^frac{3}{4} |S|^frac{1}{4}), the construction can be further refined in order to get a polynomial query time. We also consider the approximate additive setting, and show a family of DSOs that exhibits a tradeoff between the additive stretch and the size of the oracle. Finally, for the meaningful single-source case, the above result is complemented by a lower bound conditioned on the Set-Intersection conjecture. This lower bound establishes a separation between the oracle and the subgraph settings. (2) FTP: We show the construction of a path-reporting DSO of size tilde{O}(n^{4/3}(|S||T|)^{1/3}) reporting pi_{G-e}(s,t) in O(|pi_{G-e}(s,t)|+(n|S||T|)^{1/3}) time. Such a DSO can be transformed into a FTP having the same size, and moreover it can be elaborated in order to make it optimal (up to a poly-logarithmic factor) both in space and query time for the special case in which T=V(G). Our FTP improves over previous constructions when |T|=O(sqrt{|S|n}) (up to inverse poly-logarithmic factors). (3) Routing and Labeling Schemes: For the well-studied single-source setting, we present a novel routing scheme, that allows to route messages on pi_{G-e}(s,t) by using edge labels and routing tables of size tilde{O}(\sqrt{n}), and a header message of poly-logarithmic size. We also present a labeling scheme for the setting which is optimal in space up to constant factors.

(Delta+1)-vertex coloring is one of the most fundamental symmetry breaking graph problems, receiving tremendous amount of attention over the last decades. We consider the congested clique model where in each round, every pair of vertices can exchange O(log n) bits of information. In a recent breakthrough, Yi-Jun Chang, Wenzheng Li, and Seth Pettie [CLP-STOC'18] presented a randomized (Delta+1)-list coloring algorithm in the LOCAL model that works in O(log^*n+Det_{deg}(log log n)) rounds, where Det_{deg}(n') is the deterministic LOCAL complexity of (deg+1)-list coloring algorithm on n'-vertex graphs. Unfortunately, the CLP algorithm uses large messages and hence cannot be efficiently implemented in the congested clique model when the maximum degree Delta is large (in particular, when Delta=omega(sqrt{n})). Merav Parter [P-ICALP'18] recently provided a randomized (Delta+1)-coloring algorithm in O(log log Delta * log^* Delta) congested clique rounds based on a careful partitioning of the input graph into almost-independent subgraphs with maximum degree sqrt{n}. In this work, we significantly improve upon this result and present a randomized (Delta+1)-coloring algorithm with O(log^* Delta) rounds, with high probability. At the heart of our algorithm is an adaptation of the CLP algorithm for coloring a subgraph with o(n) vertices and maximum degree Omega(n^{5/8}) in O(log^* Delta) rounds. The approach is built upon a combination of techniques, this includes: the graph sparsification of [Parter-ICALP'18], and a palette sampling technique adopted to the CLP framework.

Graph spanners are sparse subgraphs that faithfully preserve the distances in the original graph up to small stretch. Spanner have been studied extensively as they have a wide range of applications ranging from distance oracles, labeling schemes and routing to solving linear systems and spectral sparsification. A $k$-spanner maintains pairwise distances up to multiplicative factor of $k$. It is a folklore that for every $n$-vertex graph $G$, one can construct a $(2k-1)$ spanner with $O(n^{1+1/k})$ edges. In a distributed setting, such spanners can be constructed in the standard CONGEST model using $O(k^2)$ rounds, when randomization is allowed. In this work, we consider spanner constructions in the congested clique model, and show: (1) A randomized construction of a $(2k-1)$-spanner with $\widetilde{O}(n^{1+1/k})$ edges in $O(\log k)$ rounds. The previous best algorithm runs in $O(k)$ rounds. (2) A deterministic construction of a $(2k-1)$-spanner with $\widetilde{O}(n^{1+1/k})$ edges in $O(\log k +(\log\log n)^3)$ rounds. The previous best algorithm runs in $O(k\log n)$ rounds. This improvement is achieved by a new derandomization theorem for hitting sets which might be of independent interest. (3) A deterministic construction of a $O(k)$-spanner with $O(k \cdot n^{1+1/k})$ edges in $O(\log k)$ rounds.

A fault-tolerant structure for a network is required to continue functioning following the failure of some of the network’s edges or vertices. This article addresses the problem of designing a fault-tolerant (α , β) approximate BFS structure (or FT-ABFS structure for short), namely, a subgraph H of the network G such that subsequent to the failure of some subset F of edges or vertices, the surviving part of H (namely, H \ F ) still contains an approximate BFS spanning tree for (the surviving part of) G , satisfying dist( s,v,H \ F ) ≤ α ċ dist( s,v,G \ F )+ β for every v isin V . Our first result is an algorithm that given an n -vertex unweighted undirected graph G and a source s constructs a multiplicative (3,0) FT-ABFS structure rooted at s resilient to a failure of a single edge with at most 4 n edges (improving by an O (log n ) factor on the near-tight result of Baswana and Khanna (2010) for the special case of edge failures). This was recently improved to 2n edges by Bilò et al. (2014). Next, we consider the multiple edge faults case, for a constant integer f >1, we prove that there exists a (polynomial-time constructible) (3 f , f log n ) FT-ABFS structure with O ( f n ) edges that is resilient against f faults. We also show the existence of a (3 f +1,0) FT-ABFS structure with O ( f log f n ċ n ) edges. We then consider additive (1, β ) FT-ABFS structures and demonstrate an interesting dichotomy between multiplicative and additive spanners. In contrast to the linear size of ( α ,0) FT-ABFS structures, we show that for every n , there exist δ , ε >0, and n -vertex graphs G with a source s for which any (1, n δ ) FT-ABFS structure rooted at s has Ω ( n 7/6 −ε) edges. For the case of additive stretch 3, we show that (1,3) FT-ABFS structures admit a lower bound of Ω ( n 5/4 ) edges.

Preservers and additive spanners are sparse (hence cheap to store) subgraphs that preserve the distances between given pairs of nodes exactly or with some small additive error, respectively. Since real-world networks are prone to failures, it makes sense to study fault-tolerant versions of the above structures. This turns out to be a surprisingly difficult task. For every small but arbitrary set of edge or vertex failures, the preservers and spanners need to contain replacement paths around the faulted set. Unfortunately, the complexity of the interaction between replacement paths blows up significantly, even from 1 to 2 faults, and the structure of optimal preservers and spanners is poorly understood. In particular, no nontrivial bounds for preservers and additive spanners are known when the number of faults is bigger than 2. Even the answer to the following innocent question is completely unknown: what is the worst-case size of a preserver for a single pair of nodes in the presence of f edge faults? There are no super-linear lower bounds, nor subquadratic upper bounds for f>2. In this paper we make substantial progress on this and other fundamental questions: - We present the first truly sub-quadratic size fault-tolerant single-pair preserver in unweighted (possibly directed) graphs: for any n node graph and any fixed number f of faults, O~(fn^{2-1/2^f}) size suffices. Our result also generalizes to the single-source (all targets) case, and can be used to build new fault-tolerant additive spanners (for all pairs). - The size of the above single-pair preserver grows to O(n^2) for increasing f. We show that this is necessary even in undirected unweighted graphs, and even if you allow for a small additive error: If you aim at size O(n^{2-eps}) for \eps>0, then the additive error has to be \Omega(eps f). This surprisingly matches known upper bounds in the literature. - For weighted graphs, we provide matching upper and lower bounds for the single pair case. Namely, the size of the preserver is Theta(n^2) for f > 1 in both directed and undirected graphs, while for f=1 the size is Theta(n) in undirected graphs. For directed graphs, we have a superlinear upper bound and a matching lower bound. Most of our lower bounds extend to the distance oracle setting, where rather than a subgraph we ask for any compact data structure.

We initiate a line of investigation into biological neural networks from an algorithmic perspective. We develop a simplified but biologically plausible model for distributed computation in stochastic spiking neural networks and study tradeoffs between computation time and network complexity in this model. Our aim is to abstract real neural networks in a way that, while not capturing all interesting features, preserves high-level behavior and allows us to make biologically relevant conclusions. In this paper, we focus on the important 'winner-take-all' (WTA) problem, which is analogous to a neural leader election unit: a network consisting of $n$ input neurons and n corresponding output neurons must converge to a state in which a single output corresponding to a firing input (the 'winner') fires, while all other outputs remain silent. Neural circuits for WTA rely on inhibitory neurons, which suppress the activity of competing outputs and drive the network towards a converged state with a single firing winner. We attempt to understand how the number of inhibitors used affects network convergence time. We show that it is possible to significantly outperform naive WTA constructions through a more refined use of inhibition, solving the problem in O(\theta) rounds in expectation with just O(\log^{1/\theta} n) inhibitors for any \theta. An alternative construction gives convergence in O(\log^{1/\theta} n) rounds with O(\theta) inhibitors. We complement these upper bounds with our main technical contribution, a nearly matching lower bound for networks using \ge \log \log n inhibitors. Our lower bound uses familiar indistinguishability and locality arguments from distributed computing theory applied to the neural setting. It lets us derive a number of interesting conclusions about the structure of any network solving WTA with good probability, and the use of randomness and inhibition within such a network.

We present a randomized distributed algorithm that computes a Depth-First Search (DFS) tree in ~O(D) rounds, in any planar network G=(V,E) with diameter D, with high probability. This is the first sublinear-time distributed DFS algorithm, improving on a three decades-old O(n) algorithm of Awerbuch (1985), which remains the best known for general graphs. Furthermore, this ~O(D) round complexity is nearly-optimal as Omega(D) is a trivial lower bound. A key technical ingredient in our results is the development of a distributed method for (recursively) computing a separator path, which is a path whose removal from the graph leaves connected components that are all a constant factor smaller. We believe that the general method we develop for computing path separators recursively might be of broader interest, and may provide the first step towards solving many other problems.

Graph spanners are fundamental graph structures with a wide range of applications in distributed networks. We consider a standard synchronous message passing model where in each round O(log n) bits can be transmitted over every edge (the CONGEST model). The state of the art of deterministic distributed spanner constructions suffers from large messages. The only exception is the work of Derbel et al., which computes an optimal-sized (2k-1)-spanner but uses O(n^(1-1/k)) rounds. In this paper, we significantly improve this bound. We present a deterministic distributed algorithm that given an unweighted n-vertex graph G = (V,E) and a parameter k > 2, constructs a (2k-1)-spanner with O(k n^(1+1/k)) edges within O(2^k n^(1/2 - 1/k)) rounds for every even k. For odd k, the number of rounds is O(2^k n^(1/2 - 1/(2k))). For the weighted case, we provide the first deterministic construction of a 3-spanner with O(n^(3/2)) edges that uses O(log n)-size messages and ~O(1) rounds. If the vertices have IDs in [1,Theta(n)], the spanner is computed in only 2 rounds!

We study distributed algorithms implemented in a simplified biologically inspired model for stochastic spiking neural networks. We focus on tradeoffs between computation time and network complexity, along with the role of randomness in efficient neural computation. It is widely accepted that neural computation is inherently stochastic. In recent work, we explored how this stochasticity could be leveraged to solve the `winner-take-all' leader election task. Here, we focus on using randomness in neural algorithms for similarity testing and compression. In the most basic setting, given two $n$-length patterns of firing neurons, we wish to distinguish if the patterns are equal or $ε$-far from equal. Randomization allows us to solve this task with a very compact network, using $O \left (\frac{\sqrt{n}\log n}ε\right)$ auxiliary neurons, which is sublinear in the input size. At the heart of our solution is the design of a $t$-round neural random access memory, or indexing network, which we call a neuro-RAM. This module can be implemented with $O(n/t)$ auxiliary neurons and is useful in many applications beyond similarity testing. Using a VC dimension-based argument, we show that the tradeoff between runtime and network size in our neuro-RAM is nearly optimal. Our result has several implications -- since our neuro-RAM can be implemented with deterministic threshold gates, it shows that, in contrast to similarity testing, randomness does not provide significant computational advantages for this problem. It also establishes a separation between feedforward networks whose gates spike with sigmoidal probability functions, and well-studied deterministic sigmoidal networks, whose gates output real number sigmoidal values, and which can implement a neuro-RAM much more efficiently.

We present a randomized algorithm that computes a Minimum Spanning Tree (MST) in O(log* n) rounds, with high probability, in the Congested Clique model of distributed computing. In this model, the input is a graph on n nodes, initially each node knows only its incident edges, and per round each two nodes can exchange O(log n) bits. Our key technical novelty is an O(log* n) Graph Connectivity algorithm, the heart of which is a (recursive) forest growth method, based on a combination of two ideas: a sparsity-sensitive sketching aimed at sparse graphs and a random edge sampling aimed at dense graphs. Our result improves significantly over the O(log log log n) algorithm of Hegeman et al. [PODC 2015] and the O(log log n) algorithm of Lotker et al. [SPAA 2003; SICOMP 2005].

Consider n anonymous nodes each initially supporting an opinion in {1, 2, …, k} and suppose that they should all learn the opinion with the largest support. Per round, each node contacts a random other node and exchanges B bits with it, where typically B is at most O(log n).

A distributed task is local if its time complexity is (nearly) constant, otherwise it is global. Unfortunately, local tasks are relatively scarce, and most distributed tasks require time at least logarithmic in the network size (and often higher than that). In a dynamic setting, i.e., when the network undergoes repeated and frequent topological changes, such as vertex and edge insertions and deletions, it is desirable to be able to perform a local update procedure around the modified part of the network, rather than running a static global algorithm from scratch following each change. This paper makes a step towards establishing the hypothesis that many (statically) non-local distributed tasks are local-on-average in the dynamic setting, namely, their amortized time complexity is O(log* n). Towards establishing the plausibility of this hypothesis, we propose a strategy for transforming static O(polylog(n)) time algorithms into dynamic O(log* n) amortized time update procedures. We then demonstrate the usefulness of our strategy by applying it to several fundamental problems whose static time complexity is logarithmic, including forest-decomposition, edge-orientation and coloring sparse graphs, and show that their amortized time complexity in the dynamic setting is indeed O(log* n).

Tree structures such as breadth-first search (BFS) trees and minimum spanning trees (MST) are among the most fundamental graph structures in distributed network algorithms. However, by definition, these structures are not robust against failures and even a single edge's removal can disrupt their functionality. A well-studied concept which attempts to circumvent this issue is Fault-Tolerant Tree Structures, where the tree gets augmented with additional edges from the network so that the functionality of the structure is maintained even when an edge fails. These structures, or other equivalent formulations, have been studied extensively from a centralized viewpoint. However, despite the fact that the main motivations come from distributed networks, their distributed construction has not been addressed before.

A fault-tolerant structure for a network is required for continued functioning following the failure of some of the network’s edges or vertices. This article considers breadth-first search (BFS) spanning trees and addresses the problem of designing a sparse fault-tolerant BFS structure (FT-BFS structure), namely, a sparse subgraph T of the given network G such that subsequent to the failure of a single edge or vertex, the surviving part T ′ of T still contains a BFS spanning tree for (the surviving part of) G . For a source node s , a target node t , and an edge e ∈ G , the shortest s − t path P s , t , e that does not go through e is known as a replacement path . Thus, our FT-BFS structure contains the collection of all replacement paths P s , t , e for every t ∈ V ( G ) and every failed edge e ∈ E ( G ). Our main results are as follows. We present an algorithm that for every n -vertex graph G and source node s constructs a (single edge failure) FT-BFS structure rooted at s with O ( n ċ min {Depth( s ), √n{) edges, where Depth( s ) is the depth of the BFS tree rooted at s . This result is complemented by a matching lower bound, showing that there exist n -vertex graphs with a source node s for which any edge (or vertex) FT-BFS structure rooted at s has Ω( n 3/2 ) edges. We then consider fault-tolerant multi-source BFS structures (FT-MBFS structures), aiming to provide (following a failure) a BFS tree rooted at each source s ∈ S for some subset of sources S ⊆ V . Again, tight bounds are provided, showing that there exists a poly-time algorithm that for every n -vertex graph and source set S ⊆ V of size σ constructs a (single failure) FT-MBFS structure T *( S ) from each source s i ∈ S , with O (√σ ċ n 3/2) edges, and, on the other hand, there exist n -vertex graphs with source sets S ⊆ V of cardinality σ, on which any FT-MBFS structure from S has Ω(√σ ċ n 3/2 ) edges. Finally, we propose an O (log n ) approximation algorithm for constructing FT-BFS and FT-MBFS structures. The latter is complemented by a hardness result stating that there exists no Ω(log n ) approximation algorithm for these problems under standard complexity assumptions. In comparison with previous constructions, our algorithm is deterministic and may improve the number of edges by a factor of up to √ n for some instances. All our algorithms can be extended to deal with one vertex failure as well, with the same performance.

Theoretical study of optimization problems in wireless communication often deals with zero-dimensional tasks. For example, the power control problem requires computing a power assignment guaranteeing that each transmitting station is successfully received at a single receiver point. This paper aims at addressing communication applications that require handling 2-dimensional tasks (e.g., Guaranteeing successful transmission in entire regions rather than in specific points). A natural approach to such tasks is to discretize the 2-dimensional optimization domain, e.g., By sampling points within the domain. This approach, however, might incur high time and memory requirements, and moreover, it cannot guarantee exact solutions. Towards this goal, we establish the minimum principle for the SINR function with free-space path loss (i.e., When the signal decays in proportion to the square of the distance between the transmitter and receiver). We then utilize it as a discretization technique for solving two-dimensional problems in the SINR model. This approach is shown to be useful for handling optimization problems over two dimensions (e.g., Power control, energy minimization), in providing tight bounds on the number of null-cells in the reception map, and in approximating geometrical and topological properties of the wireless reception map (e.g., Maximum inscribed sphere). Essentially, the minimum principle allows us to reduce the dimension of the optimization domain without losing anything in the accuracy or quality of the solution. More specifically, when the two dimensional optimization domain is bounded and free from any interfering station, the minimum principle implies that it is sufficient to optimize over the boundary of the domain, as the "hardest" points to be satisfied reside on boundary and not in the interior. We believe that the minimum principle, as well as the interplay between continuous and discrete analysis presented in this paper, may pave the way to future study of algorithmic SINR in higher dimensions.

We study breadth-first search (BFS) spanning trees, and address the problem of designing a sparse fault-tolerant BFS structure, or FT-BFS for short, resilient to the failure of up to two edges in the given unweighted undirected graph G, i.e., a sparse subgraph H of G such that subsequent to the failure of up to two edges, the surviving part H' of H still contains a BFS spanning tree for (the surviving part of) G. FT-BFS structures, as well as the related notion of replacement paths, have been studied so far for the restricted case of a single failure. It has been noted widely that when concerning shortest-paths in a variety of contexts, there is a sharp qualitative difference between a single failure and two or more failures. Our main results are as follows. We present an algorithm that for every n-vertex unweighted undirected graph G and source node s constructs a (two edge failure) FT-BFS structure rooted at s with O(n5/3) edges. To provide a useful theory of shortest paths avoiding 2 edges failures, we take a principled approach to classifying the arrangement these paths. We believe that the structural analysis provided in this paper may decrease the barrier for understanding the general case of f ≥ 2 faults and pave the way to the future design of f-fault resilient structures for f ≥ 2. We also provide a matching lower bound, which in fact holds for the general case of f ≥ 1 and multiple sources S ⊆ V. It shows that for every f ≥ 1, and integer 1 ≤ σ ≤ n, there exist n-vertex graphs with a source set S ⊆ V of cardinality σ for which any FT-BFS structure rooted at each s ∈ S, resilient to up to f-edge faults has Ω(σ1/(f+1) ⋅ n2-1/(f+1)) edges. In particular, for f=2 and σ=1, a dual failure FT-BFS structure rooted at s must have Ω(n5/3) edges in the worst case. Finally, we also consider the optimization variant for this problem, and propose an O(log n) approximation algorithm for constructing FT-BFS structures resilient to up to f-faults for any constant f ≥ 1 and any source set S ⊆ V.

This paper initiates the study of fault resilient network structures that mix two orthogonal protection mechanisms:(a) backup, namely, augmenting the structure with many (redundant) low-cost but fault-prone components, and (b) reinforcement, namely, acquiring high-cost but fault-resistant components. To study the trade-off between these two mechanisms in a concrete setting, we address the problem of designing a (b,r) fault-tolerant BFS (or (b,r) FT-BFS for short) structure,namely, a subgraph H of the network G consisting of two types of edges: a set E' ⊆ E of r(n) fault-resistant reinforcement edges, which are assumed to never fail, and a (larger) set E(H) \ E' of b(n) fault-prone backup edges, such that subsequent to the failure of a single fault-prone backup edge e ∈ E \ E', the surviving part of H still contains a BFS spanning tree for (the surviving part of) G, satisfying dist(s,v,H\{e}) ≤ dist(s,v,G \{e}) for every v ∈ V and e ∈ E \ E'.We establish the following tradeoff: For every real ε ∈ (0,1], if r(n) = Θ(n1-ε),then b(n) = Θ(n{1+ε) is necessary and sufficient.More specifically, as shown in ESA'13, for ε=1, FT-BFS structures (with no reinforced edges) require Θ(n3/2) edges, and this is sufficient. At the other extreme, if ε=0, then n-1 reinforced edges suffice (with no need for backup). Here, we present a polynomial time algorithm that given an undirected graph G=(V,E), a source vertex s and a real ε ∈ (0,1], constructs a (b(n),r(n)) FT-BFS with r(n) = O(n1-ε) and b(n) = O(min{1/ε • n1+ε • log n, n3/2). We complement this result by providing a nearly matching lower bound, showing that there are n-vertex graphs for which any (b(n),r(n)) FT-BFS structure requires Ω(min{n{1+ε, n3/2}) backup edges when r(n)=Ω(n1-ε) edges are reinforced.

This article studies the topological properties of wireless communication maps and their usability in algorithmic design. We consider the SINR model, which compares the received power of a signal at a receiver against the sum of strengths of other interfering signals plus background noise. To describe the behavior of a multistation network, we use the convenient representation of a reception map, which partitions the plane into reception zones, one per station, and the complementary region of the plane where no station can be heard. SINR diagrams have been studied in Avin et al. [2009] for the specific case where all stations use the same power. It was shown that the reception zones are convex (hence connected) and fat, and this was used to devise an efficient algorithm for the fundamental problem of point location. Here we consider the more general (and common) case where transmission energies are arbitrary (or nonuniform). Under that setting, the reception zones are not necessarily convex or even connected. This poses the algorithmic challenge of designing efficient point location techniques for the nonuniform setting, as well as the theoretical challenge of understanding the geometry of SINR diagrams (e.g., the maximal number of connected components they might have). Our key result exhibits a striking contrast between d - and ( d +1)-dimensional maps for a network embedded in d -dimensional space. Specifically, it is shown that whereas the d -dimensional map might be highly fractured, drawing the map in one dimension higher “heals” the zones, which become connected (in fact, hyperbolically connected). We also provide bounds for the fatness of reception zones. Subsequently, we consider algorithmic applications and propose a new variant of approximate point location.

A fault-tolerant structure for a network is required to continue functioning following the failure of some of the network's edges or vertices. This paper addresses the problem of designing a fault-tolerant (α, β) approximate BFS structure (or FT-ABFS structure for short), namely, a subgraph H of the network G such that subsequent to the failure of some subset F of edges or vertices, the surviving part of H still contains an approximate BFS spanning tree for (the surviving part of) G, satisfying dist(s, v, H\F) ≤ α-dist(s, v, G\F)+β for every v ∊ V. We first consider multiplicative (α, 0) FT-ABFS structures resilient to a failure of a single edge or vertex, and present an algorithm that given an n-vertex unweighted undirected graph G and a source s constructs a (3,0) FT-ABFS structure rooted at s with at most 3n edges (improving by an O(logn) factor on the near-tight result of [3]). Assuming at most f edge failures, for constant integer f > 1, we prove that there exists a (poly-time constructible) (3(f +1), (f +1) logn) FT-ABFS structure with O(fn) edges. We then consider additive (1, β) FT-ABFS structures. In contrast to the linear size of (α, 0) FT-ABFS structures, we show that for every β ∊ [1,O(logn)] there exists an n-vertex graph G with a source s for which any (1, β) FT-ABFS structure rooted at s has Ω(n1+∊(β)) edges, for some function ∊(β) ∊ (0,1). In particular, (1,3) FT-ABFS structures admit a lower bound of Ω(n5/4) edges. These lower bounds demonstrate an interesting dichotomy between multiplicative and additive spanners; whereas (α, 0) FT-ABFS structures of size O(n) exist (for α ≥ 3), their additive counterparts, (1,β) FT-ABFS structures, are of super-linear size. Our lower bounds are complemented by an upper bound, showing that there exists a poly-time algorithm that for every n-vertex unweighted undirected graph G and source s constructs a (1,4) FT-ABFS structure rooted at s with at most O(n4/3) edges.

The celebrated Perron–Frobenius (PF) theorem is stated for irreducible nonnegative square matrices, and provides a simple characterization of their eigenvectors and eigenvalues. The importance of this theorem stems from the fact that eigenvalue problems on such matrices arise in many fields of science and engineering, including dynamical systems theory, economics, statistics and optimization. However, many real-life scenarios give rise to nonsquare matrices. Despite the extensive development of spectral theories for nonnegative matrices, the applicability of such theories to non-convex optimization problems is not clear. In particular, a natural question is whether the PF Theorem (along with its applications) can be generalized to a nonsquare setting. Our paper provides a generalization of the PF Theorem to nonsquare multiple choice matrices. The extension can be interpreted as representing systems with additional degrees of freedom, where each client entity may choose between multiple servers that can cooperate in serving it (while potentially interfering with other clients). This formulation is motivated by applications to power control in wireless networks, economics and others, all of which extend known examples for the use of the original PF Theorem. We show that the option of cooperation does not improve the situation, in the sense that in the optimum solution, no cooperation is needed, and only one server per client entity needs to work. Hence, the additional power of having several potential servers per client translates into choosing the “best” single server and not into sharing the load between the servers in some way, as one might have expected. The two main contributions of the paper are (i) a generalized PF Theorem that characterizes the optimal solution for a non-convex problem, and (ii) an algorithm for finding the optimal solution in polynomial time. In addition, we extend the definitions of irreducibility and largest eigenvalue of square matrices to nonsquare ones in a novel and non-trivial way, which turns out to be necessary and sufficient for our generalized theorem to hold. To characterize the optimal solution, we use techniques from a wide range of areas. In particular, the analysis exploits combinatorial properties of polytopes, graph-theoretic techniques and analytic tools such as spectral properties of nonnegative matrices and root characterization of integer polynomials.

This paper studies the reception zones of a wireless network in the SINR model with receivers that employ interference cancellation (IC). IC is a recently developed technique that allows a receiver to decode interfering signals, and cancel them from the received signal in order to decode its intended message. We first derive the important topological properties of the reception zones and their relation to high-order Voronoi diagrams and other geometric objects. We then discuss the computational issues that arise when seeking an efficient description of the zones. Our main fundamental result states that although potentially there are exponentially many possible cancellation orderings, and as a result, reception zones, in fact there are much fewer nonempty such zones. We prove a linear bound (hence tight) on the number of zones and provide a polynomial time algorithm to describe the diagram. Moreover, we introduce a novel parameter, the Compactness Parameter, which influences the tightness of our bounds. We then utilize these properties to devise a logarithmic time algorithm to answer point-location queries for networks with IC.

The power control problem for wireless networks in the SINR model requires determining the optimal power assignment for a set of communication requests such that the SINR threshold is met for all receivers. If the network topology is known to all participants, then it is possible to compute an optimal power assignment in polynomial time. In realistic environments, however, such global knowledge is usually not available to every node. In addition, protocols that are based on global computation cannot support mobility and hardly adapt when participants dynamically join or leave the system. In this paper we present and analyze a fully distributed power control protocol that is based on local information. For a set of communication pairs, each consisting of a sender node and a designated receiver node, the algorithm enables the nodes to converge to the optimal power assignment (if there is one under the given constraints) quickly with high probability. Two types of bounded resources are considered, namely, the maximal transmission energy and the maximum distance between any sender and receiver. It is shown that the restriction to local computation increases the convergence rate by only a multiplicative factor of O(log n + log log Ψmax), where Ψmaxis the maximal power constraint of the network. If the diameter of the network is bounded by Lmaxthen the increase in convergence rate is given by O(log n + log log Lmax).

In this paper we study the topological properties of wireless communication maps and their usability in algorithmic design. We consider the SINR model, which compares the received power of a signal at a receiver against the sum of strengths of other interfering signals plus background noise. To describe the behavior of a multi-station network, we use the convenient representation of a reception map. In the SINR model, the resulting SINR diagram partitions the plane into reception zones, one per station, and the complementary region of the plane where no station can be heard. SINR diagrams have been studied in [3] for the specific case where all stations use the same power. It is shown that the reception zones are convex (hence connected) and fat, and this is used to devise an efficient algorithm for the fundamental problem of point location. Here we consider the more general (and common) case where transmission energies are arbitrary (or non-uniform). Under that setting, the reception zones are not necessarily convex or even connected. This poses the algorithmic challenge of designing efficient point location techniques for the non-uniform setting, as well as the theoretical challenge of understanding the geometry of SINR diagrams (e.g., the maximal number of connected components they might have). We achieve several results in both directions. We establish a form of weaker convexity in the case where stations are aligned on a line and use this to derive a tight bound on the number of connected components in this case. In addition, one of our key results concerns the behavior of a (d+1)-dimensional map, i.e., a map in one dimension higher than the dimension in which stations are embedded. Specifically, although the d-dimensional map might be highly fractured, drawing the map in one dimension higher "heals" the zones, which become connected (in fact hyperbolically connected). In addition, as a step toward establishing a weaker form of convexity for the d-dimensional map, we study the interference function and show that it satisfies the maximum principle. This is done through an analysis technique based on looking at the behavior of systems composed on lines of densely placed weak stations, as the number of stations tends to infinity, keeping their total transmission energy fixed. Finally, we turn to consider algorithmic applications, and propose a new variant of approximate point location.

One of the striking features of evolution is the appearance of novel structures in organisms. Recently, Kirschner and Gerhart have integrated discoveries in evolution, genetics, and developmental biology to form a theory of facilitated variation (FV). The key observation is that organisms are designed such that random genetic changes are channeled in phenotypic directions that are potentially useful. An open question is how FV spontaneously emerges during evolution. Here, we address this by means of computer simulations of two well-studied model systems, logic circuits and RNA secondary structure. We find that evolution of FV is enhanced in environments that change from time to time in a systematic way: the varying environments are made of the same set of subgoals but in different combinations. We find that organisms that evolve under such varying goals not only remember their history but also generalize to future environments, exhibiting high adaptability to novel goals. Rapid adaptation is seen to goals composed of the same subgoals in novel combinations, and to goals where one of the subgoals was never seen in the history of the organism. The mechanisms for such enhanced generation of novelty (generalization) are analyzed, as is the way that organisms store information in their genomes about their past environments. Elements of facilitated variation theory, such as weak regulatory linkage, modularity, and reduced pleiotropy of mutations, evolve spontaneously under these conditions. Thus, environments that change in a systematic, modular fashion seem to promote facilitated variation and allow evolution to generalize to novel conditions.