BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Merav Parter

Merav Parter appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsDistributed, Parallel, and Cluster ComputingNetworking and Internet ArchitectureComputational ComplexityComputational GeometryComputer Science and Game TheoryInformation Theorymath.ITNeural and Evolutionary ComputingNeurons and CognitionNumerical Analysis

Catalog footprint

What is connected

25works
11topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

25 published item(s)

preprint2022arXiv

Broadcast CONGEST Algorithms against Adversarial Edges

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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Õptimal Dual Vertex Failure Connectivity Labels

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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Õptimal Vertex Fault-Tolerant Spanners in Õptimal Time: Sequential, Distributed and Parallel

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 provide algorithms for computing nearly optimal $f$-VFT spanners for any $n$-vertex $m$-edge graph, with near optimal running time in several computational models: - A randomized sequential algorithm with a runtime of $\widetilde{O}(m)$ (i.e., independent in the number of faults $f$). The state-of-the-art time bound is $\widetilde{O}(f^{1-1/k}\cdot n^{2+1/k}+f^2 m)$ by [Bodwin, Dinitz and Robelle, SODA 2021]. - A distributed congest algorithm of $\widetilde{O}(1)$ rounds. Improving upon [Dinitz and Robelle, PODC 2020] that obtained FT spanners with near-optimal sparsity in $\widetilde{O}(f^{2})$ rounds. - A PRAM (CRCW) algorithm with $\widetilde{O}(m)$ work and $\widetilde{O}(1)$ depth. Prior bounds implied by [Dinitz and Krauthgamer, PODC 2011] obtained sub-optimal FT spanners using $\widetilde{O}(f^3m)$ work and $\widetilde{O}(f^3)$ depth. An immediate corollary provides the first nearly-optimal PRAM algorithm for computing nearly optimal $λ$-\emph{vertex} connectivity certificates using polylogarithmic depth and near-linear work. This improves the state-of-the-art parallel bounds of $\widetilde{O}(1)$ depth and $O(λm)$ work, by [Karger and Motwani, STOC'93].

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

$(Δ+1)$ Coloring in the Congested Clique Model

In this paper, we present improved algorithms for the $(Δ+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 $(Δ+1)$ vertex coloring algorithm that works in $O(\log\log Δ\cdot \log^* Δ)$-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) $(Δ+1)$-coloring for $Δ=O((n/\log n)^{1-ε})$ for any $ε\in (0,1)$, within $O(\log(1/ε)\log^* Δ)$ rounds, and (2) $(Δ+Δ^{1/2+o(1)})$-coloring within $O(\log^* Δ)$ rounds. Turning to deterministic algorithms, we show a $(Δ+1)$-coloring algorithm that works in $O(\log Δ)$ rounds.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Exponentially Faster Shortest Paths in the Congested Clique

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(\sqrt{n})$ sources. -- $(2+ε)$-approximation of all pairs shortest paths (APSP). -- $(1+ε,β)$-approximation of APSP where $β=O(\frac{\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(\fracβε)$ where $β=O(\frac{\log\log n}ε)^{\log\log n}$. Handling the long distances is done by devising a new algorithm for computing 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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space

The Massively Parallel Computation (MPC) model is an emerging model which distills core aspects of distributed and parallel computation. It has been developed as a tool to solve (typically graph) problems in systems where the input is distributed over many machines with limited space. Recent work has focused on the regime in which machines have sublinear (in $n$, the number of nodes in the input graph) memory, with randomized algorithms presented for fundamental graph problems of Maximal Matching and Maximal Independent Set. However, there have been no prior corresponding \emph{deterministic} algorithms. A major challenge underlying the sublinear space setting is that the local space of each machine might be too small to store all the edges incident to a single node. This poses a considerable obstacle compared to the classical models in which each node is assumed to know and have easy access to its incident edges. To overcome this barrier we introduce a new \emph{graph sparsification technique} that \emph{deterministically} computes a low-degree subgraph with additional desired properties. Using this framework to derandomize the well-known randomized algorithm of Luby [SICOMP'86], we obtain $O(\log Δ+\log\log n)$-round \emph{deterministic} MPC algorithms for solving the fundamental problems of \emph{Maximal Matching} and \emph{Maximal Independent Set} with $O(n^ε)$ space on each machine for any constant $ε> 0$. Based on the recent work of Ghaffari et al. [FOCS'18], this additive $O(\log\log n)$ factor is \emph{conditionally} essential. These algorithms can also be shown to run in $O(\log Δ)$ rounds in the closely related model of \congc, improving upon the state-of-the-art bound of $O(\log^2 Δ)$ rounds by Censor-Hillel et al. [DISC'17].

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

New $(α,β)$ Spanners and Hopsets

An $f(d)$-spanner of an unweighted $n$-vertex graph $G=(V,E)$ is a subgraph $H$ satisfying that $dist_H(u, v)$ is at most $f(dist_G(u, v))$ for every $u,v \in V$. We present new spanner constructions that achieve a nearly optimal stretch of $O(\lceil k /d \rceil)$ for any distance value $d \in [1,k^{1-o(1)}]$, and $d \geq k^{1+o(1)}$. We show the following: 1. There exists an $f(d)$-spanner $H \subseteq G$ with $f(d)\leq 7k$ for any $d \in [1,\sqrt{k}/2]$ with expected size $O_{k}(n^{1+1/k})$. This in particular gives $(α,β)$ spanners with $α=O(\sqrt{k})$ and $β=O(k)$. 2. For any $ε\in (0,1/2]$, there exists an $(α,β)$-spanner with $α=O(k^ε)$, $β=O_ε(k)$ and of expected size $O_{k}(n^{1+1/k})$. This implies a stretch of $O(\lceil k/d \rceil)$ for any $d \in [\sqrt{k}/2, k^{1-ε}]$, and for every $d\geq k^{1+ε}$. In particular, it provides a constant stretch already for vertex pairs at distance $k^{1+o(1)}$ (improving upon $d=(\log k)^{\log k}$ that was known before). Up to the $o(1)$ factor in the exponent, and the constant factor in the stretch, this is the best possible by the girth argument. 3. For any $ε\in (0,1)$ and integer $k\geq 1$, there is a $(3+ε, β)$-spanner with $β=O_ε(k^{\log(3+8/ε)})$ and $O_{k,ε}(n^{1+1/k})$ edges. We also consider the related graph concept of hopsets introduced by [Cohen, J. ACM '00]. We present a new family of $(α,β)$ hopsets with $\widetilde{O}(k \cdot n^{1+1/k})$ edges and $α\cdot β=O(k)$. Most notably, we show a construction of $(3+ε,β)$ hopset with $\widetilde{O}_{k,ε}(n^{1+1/k})$ edges and hop-bound of $β=O_ε(k^{\log(3+9/ε)})$, improving upon the state-of-the-art hop-bound of $β=O(\log k /ε)^{\log k}$ by [Elkin-Neiman, '17] and [Huang-Pettie, '17].

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On Packing Low-Diameter Spanning Trees

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 $\cal{T}$ of $\lfloor k/2 \rfloor$ edge-disjoint spanning trees, that we refer to as a tree packing; the diameter of the tree packing $\cal{T}$ is the largest diameter of any tree in $\cal{T}$. A desirable property of a tree packing, that is both sufficient and necessary for leveraging the high connectivity of a graph in distributed communication, is that its diameter is low. Yet, despite extensive research in this area, it is still unclear how to compute a tree packing, whose diameter is sublinear in $|V(G)|$, in a low-diameter graph $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. First, we show that, for every $k$-edge connected $n$-vertex graph $G$ of diameter $D$, there is a tree packing $\cal{T}$ of size $Ω(k)$, diameter $O((101k\log n)^D)$, that causes edge-congestion at most $2$. Second, we show that for every $k$-edge connected $n$-vertex graph $G$ of diameter $D$, the diameter of $G[p]$ is $O(k^{D(D+1)/2})$ with high probability, where $G[p]$ is obtained by sampling each edge of $G$ independently with probability $p=Θ(\log n/k)$. This provides a packing of $Ω(k/\log n)$ edge-disjoint trees of diameter at most $O(k^{(D(D+1)/2)})$ each. We then prove that these two results are nearly tight. Lastly, we show that if every pair of vertices in a graph has $k$ edge-disjoint paths of length at most $D$ connecting them, then there is a tree packing of size $k$, diameter $O(D\log n)$, causing edge-congestion $O(\log n)$. We also provide several applications of low-diameter tree packing in distributed computation.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Simple, Deterministic, Constant-Round Coloring in the Congested Clique

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). 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 et al. (STOC'18), 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 (MPC) model provided that each machine has linear (in $n$, the number of nodes in the input graph) space. We also show an extension of our algorithm to the MPC regime in which machines have sublinear space: we present the first deterministic $(Δ+1)$-list coloring algorithm designed for sublinear-space MPC, which runs in $O(\log Δ+ \log\log n)$ rounds.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Small Cuts and Connectivity Certificates: A Fault Tolerant Approach

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 $\widetilde{O}(1)$ rounds) for problems that are closely related to hard global problems (i.e., with a lower bound of $Ω(Diam+\sqrt{n})$ rounds). Our main results are: (1) For $D$-diameter unweighted graphs with constant edge connectivity, we show an exact distributed deterministic computation of the minimum cut in $poly(D)$ rounds. This resolves one the open problems recently raised in Daga, Henzinger, Nanongkai and Saranurak, STOC'19. (2) For $D$-diameter unweighted graphs, we present a deterministic algorithm that computes of all edge connectivities up to constant in $poly(D)\cdot 2^{O(\sqrt{\log n\log\log n})}$ rounds. (3) Computation of sparse $λ$ connectivity certificates in $\widetilde{O}(λ)$ rounds. Previous constructions where known only for $λ\leq 3$ and required $O(D)$ rounds. This resolves the problem raised by Dori PODC'18.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Computational Tradeoffs in Biological Neural Networks: Self-Stabilizing Winner-Take-All Networks

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(θ)$ rounds in expectation with just $O(\log^{1/θ} n)$ inhibitors for any $θ$. An alternative construction gives convergence in $O(\log^{1/θ} n)$ rounds with $O(θ)$ inhibitors. We compliment 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. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Derandomizing Local Distributed Algorithms under Bandwidth Restrictions

This paper addresses the cornerstone family of \emph{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. We combine bounded independence, which we show to be sufficient for some algorithms, with the method of conditional expectations and with additional machinery, to obtain the following results. Our techniques give a deterministic maximal independent set (MIS) algorithm in the CONGEST model, where the communication graph is identical to the input graph, in $O(D\log^2 n)$ rounds, where $D$ is the diameter of the graph. The best known running time in terms of $n$ alone is $2^{O(\sqrt{\log n})}$, which is super-polylogarithmic, and requires large messages. For the CONGEST model, the only known previous solution is a coloring-based $O(Δ+ \log^* n)$-round algorithm, where $Δ$ is the maximal degree in the graph. On the way to obtaining the above, we show that in the \emph{Congested Clique} model, which allows all-to-all communication, there is a deterministic MIS algorithm that runs in $O(\log Δ\log n)$ rounds.%, where $Δ$ is the maximum degree. When $Δ=O(n^{1/3})$, the bound improves to $O(\log Δ)$ and holds also for $(Δ+1)$-coloring. In addition, we deterministically construct a $(2k-1)$-spanner with $O(kn^{1+1/k}\log n)$ edges in $O(k \log n)$ rounds. For comparison, in the more stringent CONGEST model, the best deterministic algorithm for constructing a $(2k-1)$-spanner with $O(kn^{1+1/k})$ edges runs in $O(n^{1-1/k})$ rounds.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Computing in Additive Networks with Bounded-Information Codes

This paper studies the theory of the additive wireless network model, in which the received signal is abstracted as an addition of the transmitted signals. Our central observation is that the crucial challenge for computing in this model is not high contention, as assumed previously, but rather guaranteeing a bounded amount of \emph{information} in each neighborhood per round, a property that we show is achievable using a new random coding technique. Technically, we provide efficient algorithms for fundamental distributed tasks in additive networks, such as solving various symmetry breaking problems, approximating network parameters, and solving an \emph{asymmetry revealing} problem such as computing a maximal input. The key method used is a novel random coding technique that allows a node to successfully decode the received information, as long as it does not contain too many distinct values. We then design our algorithms to produce a limited amount of information in each neighborhood in order to leverage our enriched toolbox for computing in additive networks.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Dual Failure Resilient BFS Structure

We study {\em breadth-first search (BFS)} spanning trees, and address the problem of designing a sparse {\em fault-tolerant} BFS structure, or {\em FT-BFS } for short, resilient to the failure of up to two edges in the given undirected unweighted 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(n^{5/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\geq 2$ faults and pave the way to the future design of $f$-fault resilient structures for $f \geq 2$. We also provide a matching lower bound, which in fact holds for the general case of $f \geq 1$ and multiple sources $S \subseteq V$. It shows that for every $f\geq 1$, and integer $1 \leq σ\leq n$, there exist $n$-vertex graphs with a source set $S \subseteq V$ of cardinality $σ$ for which any FT-BFS structure rooted at each $s \in S$, resilient to up to $f$-edge faults has $Ω(σ^{1/(f+1)} \cdot n^{2-1/(f+1)})$ edges.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Fault Tolerant BFS Structures: A Reinforcement-Backup Tradeoff

This paper initiates the study of fault resilient network structures that mix two orthogonal protection mechanisms: (a) {\em backup}, namely, augmenting the structure with many (redundant) low-cost but fault-prone components, and (b) {\em 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)$ {\em 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' \subseteq E$ of $r(n)$ fault-resistant {\em reinforcement} edges, which are assumed to never fail, and a (larger) set $E(H) \setminus E'$ of $b(n)$ fault-prone {\em backup} edges, such that subsequent to the failure of a single fault-prone backup edge $e \in E \setminus E'$, the surviving part of $H$ still contains an BFS spanning tree for (the surviving part of) $G$, satisfying $dist(s,v,H\setminus \{e\}) \leq dist(s,v,G\setminus \{e\})$ for every $v \in V$ and $e \in E \setminus E'$. We establish the following tradeoff between $b(n)$ and $r(n)$: For every real $ε\in (0,1]$, if $r(n) = {\tildeΘ}(n^{1-ε})$, then $b(n) = {\tildeΘ}(n^{1+ε})$ is necessary and sufficient.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Bypassing Erdős' Girth Conjecture: Hybrid Stretch and Sourcewise Spanners

An $(α,β)$-spanner of an $n$-vertex graph $G=(V,E)$ is a subgraph $H$ of $G$ satisfying that $dist(u, v, H) \leq α\cdot dist(u, v, G)+β$ for every pair $(u, v)\in V \times V$, where $dist(u,v,G')$ denotes the distance between $u$ and $v$ in $G' \subseteq G$. It is known that for every integer $k \geq 1$, every graph $G$ has a polynomially constructible $(2k-1,0)$-spanner of size $O(n^{1+1/k})$. This size-stretch bound is essentially optimal by the girth conjecture. It is therefore intriguing to ask if one can "bypass" the conjecture by settling for a multiplicative stretch of $2k-1$ only for \emph{neighboring} vertex pairs, while maintaining a strictly \emph{better} multiplicative stretch for the rest of the pairs. We answer this question in the affirmative and introduce the notion of \emph{$k$-hybrid spanners}, in which non neighboring vertex pairs enjoy a \emph{multiplicative} $k$-stretch and the neighboring vertex pairs enjoy a \emph{multiplicative} $(2k-1)$ stretch (hence, tight by the conjecture). We show that for every unweighted $n$-vertex graph $G$ with $m$ edges, there is a (polynomially constructible) $k$-hybrid spanner with $O(k^2 \cdot n^{1+1/k})$ edges. \indent An alternative natural approach to bypass the girth conjecture is to allow ourself to take care only of a subset of pairs $S \times V$ for a given subset of vertices $S \subseteq V$ referred to here as \emph{sources}. Spanners in which the distances in $S \times V$ are bounded are referred to as \emph{sourcewise spanners}. Several constructions for this variant are provided (e.g., multiplicative sourcewise spanners, additive sourcewise spanners and more).

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Fault Tolerant Approximate BFS Structures

This paper addresses the problem of designing a {\em fault-tolerant} $(α, β)$ approximate BFS structure (or {\em 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 \emph{approximate} BFS spanning tree for (the surviving part of) $G$, satisfying $dist(s,v,H\setminus F) \leq α\cdot dist(s,v,G\setminus F)+β$ for every $v \in V$. We first consider {\em multiplicative} $(α,0)$ FT-ABFS structures resilient to a failure of a single edge 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 $4n$ edges (improving by an $O(\log n)$ factor on the near-tight result of \cite{BS10} for the special case of edge failures). 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) \log n)$ FT-ABFS structure with $O(f n)$ edges. We then consider {\em additive} $(1,β)$ FT-ABFS structures. In contrast to the linear size of $(α,0)$ FT-ABFS structures, we show that for every $β\in [1, O(\log n)]$ there exists an $n$-vertex graph $G$ with a source $s$ for which any $(1,β)$ FT-ABFS structure rooted at $s$ has $Ω(n^{1+ε(β)})$ edges, for some function $ε(β) \in (0,1)$. In particular, $(1,3)$ FT-ABFS structures admit a lower bound of $Ω(n^{5/4})$ edges. 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(n^{4/3})$ edges.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Vertex Fault Tolerant Additive Spanners

A {\em fault-tolerant} structure for a network is required to continue functioning following the failure of some of the network's edges or vertices. In this paper, we address the problem of designing a {\em fault-tolerant} additive spanner, namely, a subgraph $H$ of the network $G$ such that subsequent to the failure of a single vertex, the surviving part of $H$ still contains an \emph{additive} spanner for (the surviving part of) $G$, satisfying $dist(s,t,H\setminus \{v\}) \leq dist(s,t,G\setminus \{v\})+β$ for every $s,t,v \in V$. Recently, the problem of constructing fault-tolerant additive spanners resilient to the failure of up to $f$ \emph{edges} has been considered by Braunschvig et. al. The problem of handling \emph{vertex} failures was left open therein. In this paper we develop new techniques for constructing additive FT-spanners overcoming the failure of a single vertex in the graph. Our first result is an FT-spanner with additive stretch $2$ and $\widetilde{O}(n^{5/3})$ edges. Our second result is an FT-spanner with additive stretch $6$ and $\widetilde{O}(n^{3/2})$ edges. The construction algorithm consists of two main components: (a) constructing an FT-clustering graph and (b) applying a modified path-buying procedure suitably adopted to failure prone settings. Finally, we also describe two constructions for {\em fault-tolerant multi-source additive spanners}, aiming to guarantee a bounded additive stretch following a vertex failure, for every pair of vertices in $S \times V$ for a given subset of sources $S\subseteq V$. The additive stretch bounds of our constructions are 4 and 8 (using a different number of edges).

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Braess's Paradox in Wireless Networks: The Danger of Improved Technology

When comparing new wireless technologies, it is common to consider the effect that they have on the capacity of the network (defined as the maximum number of simultaneously satisfiable links). For example, it has been shown that giving receivers the ability to do interference cancellation, or allowing transmitters to use power control, never decreases the capacity and can in certain cases increase it by $Ω(\log (Δ\cdot P_{\max}))$, where $Δ$ is the ratio of the longest link length to the smallest transmitter-receiver distance and $P_{\max}$ is the maximum transmission power. But there is no reason to expect the optimal capacity to be realized in practice, particularly since maximizing the capacity is known to be NP-hard. In reality, we would expect links to behave as self-interested agents, and thus when introducing a new technology it makes more sense to compare the values reached at game-theoretic equilibria than the optimum values. In this paper we initiate this line of work by comparing various notions of equilibria (particularly Nash equilibria and no-regret behavior) when using a supposedly "better" technology. We show a version of Braess's Paradox for all of them: in certain networks, upgrading technology can actually make the equilibria \emph{worse}, despite an increase in the capacity. We construct instances where this decrease is a constant factor for power control, interference cancellation, and improvements in the SINR threshold ($β$), and is $Ω(\log Δ)$ when power control is combined with interference cancellation. However, we show that these examples are basically tight: the decrease is at most O(1) for power control, interference cancellation, and improved $β$, and is at most $O(\log Δ)$ when power control is combined with interference cancellation.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Generalized Perron--Frobenius Theorem for Nonsquare Matrices

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. 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 matrices. The extension can be interpreted as representing client-server systems with additional degrees of freedom, where each client 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 between servers does not improve the situation, in the sense that in the optimal solution no cooperation is needed, and only one server needs to serve each client. Hence, the additional power of having several potential servers per client translates into \emph{choosing} the best single server and not into \emph{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 nonsquare problem, and (ii) an algorithm for finding the optimal solution in polynomial time.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

SINR Diagram with Interference Cancellation

In this paper we study the reception zones of a wireless network in the SINR model with receivers that employ \emph{interference cancellation} (IC), a technique that allows a receiver to decode interfering signals, and \emph{cancel} them from the received signal in order to decode its intended message. We first derive some important topological properties of the diagram describing the reception zones and their connections to \emph{high-order Voronoi diagrams} and other related 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 consequently reception cells), in fact there are much fewer nonempty such cells. We prove a (tight) linear bound on the number of cells and provide a polynomial time algorithm to describe the diagram. Moreover, we introduce a novel measure, referred to as the \emph{Compactness Parameter}, which influences the tightness of our bounds. We then utilize the properties established for reception diagrams to devise a logarithmic time algorithm for answering \emph{point-location} queries for networks with IC.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Sparse Fault-Tolerant BFS Trees

This paper addresses the problem of designing a sparse {\em fault-tolerant} BFS tree, or {\em FT-BFS tree} for short, 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$. 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 tree rooted at $s$ with $O(n \cdot \min\{\Depth(s), \sqrt{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 tree rooted at $s$ has $Ω(n^{3/2})$ edges. We then consider {\em fault-tolerant multi-source BFS trees}, or {\em FT-MBFS trees} for short, aiming to provide (following a failure) a BFS tree rooted at each source $s\in S$ for some subset of sources $S\subseteq V$. Again, tight bounds are provided, showing that there exists a poly-time algorithm that for every $n$-vertex graph and source set $S \subseteq V$ of size $σ$ constructs a (single failure) FT-MBFS tree $T^*(S)$ from each source $s_i \in S$, with $O(\sqrtσ \cdot n^{3/2})$ edges, and on the other hand there exist $n$-vertex graphs with source sets $S \subseteq V$ of cardinality $σ$, on which any FT-MBFS tree from $S$ has $Ω(\sqrtσ\cdot 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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Randomized Distributed Decision

The paper tackles the power of randomization in the context of locality by analyzing the ability to`boost' the success probability of deciding a distributed language. The main outcome of this analysis is that the distributed computing setting contrasts significantly with the sequential one as far as randomization is concerned. Indeed, we prove that in some cases, the ability to increase the success probability for deciding distributed languages is rather limited. Informally, a (p,q)-decider for a language L is a distributed randomized algorithm which accepts instances in L with probability at least p and rejects instances outside of L with probability at least q. It is known that every hereditary language that can be decided in t rounds by a (p,q)-decider, where p^2+q>1, can actually be decided deterministically in O(t) rounds. In one of our results we give evidence supporting the conjecture that the above statement holds for all distributed languages. This is achieved by considering the restricted case of path topologies. We then turn our attention to the range below the aforementioned threshold, namely, the case where p^2+q\leq1. We define B_k(t) to be the set of all languages decidable in at most t rounds by a (p,q)-decider, where p^{1+1/k}+q>1. It is easy to see that every language is decidable (in zero rounds) by a (p,q)-decider satisfying p+q=1. Hence, the hierarchy B_k provides a spectrum of complexity classes between determinism and complete randomization. We prove that all these classes are separated: for every integer k\geq 1, there exists a language L satisfying L\in B_{k+1}(0) but L\notin B_k(t) for any t=o(n). In addition, we show that B_\infty(t) does not contain all languages, for any t=o(n). Finally, we show that if the inputs can be restricted in certain ways, then the ability to boost the success probability becomes almost null.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Secluded Connectivity Problems

Consider a setting where possibly sensitive information sent over a path in a network is visible to every {neighbor} of the path, i.e., every neighbor of some node on the path, thus including the nodes on the path itself. The exposure of a path $P$ can be measured as the number of nodes adjacent to it, denoted by $N[P]$. A path is said to be secluded if its exposure is small. A similar measure can be applied to other connected subgraphs, such as Steiner trees connecting a given set of terminals. Such subgraphs may be relevant due to considerations of privacy, security or revenue maximization. This paper considers problems related to minimum exposure connectivity structures such as paths and Steiner trees. It is shown that on unweighted undirected $n$-node graphs, the problem of finding the minimum exposure path connecting a given pair of vertices is strongly inapproximable, i.e., hard to approximate within a factor of $O(2^{\log^{1-ε}n})$ for any $ε>0$ (under an appropriate complexity assumption), but is approximable with ratio $\sqrtΔ+3$, where $Δ$ is the maximum degree in the graph. One of our main results concerns the class of bounded-degree graphs, which is shown to exhibit the following interesting dichotomy. On the one hand, the minimum exposure path problem is NP-hard on node-weighted or directed bounded-degree graphs (even when the maximum degree is 4). On the other hand, we present a polynomial algorithm (based on a nontrivial dynamic program) for the problem on unweighted undirected bounded-degree graphs. Likewise, the problem is shown to be polynomial also for the class of (weighted or unweighted) bounded-treewidth graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The Topology of Wireless Communication

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 \emph{reception map}. In the SINR model, the resulting \emph{SINR diagram} partitions the plane into reception zones, one per station, and the complementary region of the plane where no station can be heard. We consider the general 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 as well as the theoretical challenge of understanding the geometry of SINR diagrams. We achieve several results in both directions. We establish a form of weaker convexity in the case where stations are aligned on a line. In addition, one of our key results concerns the behavior of a $(d+1)$-dimensional map. Specifically, although the $d$-dimensional map might be highly fractured, drawing the map in one dimension higher "heals" the zones, which become 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. Finally, we turn to consider algorithmic applications, and propose a new variant of approximate point location.

0 citations0 reviewsNo code linkedOpen access