Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTight Network Topology Dependent Bounds on Rounds of Communication
81
0
0.0
(
0
)
Added by
Atri Rudra
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We prove tight network topology dependent bounds on the round complexity of computing well studied $k$-party functions such as set disjointness and element distinctness. Unlike the usual case in the CONGEST model in distributed computing, we fix the function and then vary the underlying network topology. This complements the recent such results on total communication that have received some attention. We also present some applications to distributed graph computation problems. Our main contribution is a proof technique that allows us to reduce the problem on a general graph topology to a relevant two-party communication complexity problem. However, unlike many previous works that also used the same high level strategy, we do not reason about a two-party communication problem that is induced by a cut in the graph. To `stitch back the various lower bounds from the two party communication problems, we use the notion of timed graph that has seen prior use in network coding. Our reductions use some tools from Steiner tree packing and multi-commodity flow problems that have a delay constraint.
rate research
Read More
Let $v(F)$ denote the number of vertices in a fixed connected pattern graph $F$. We show an infinite family of patterns $F$ such that the existence of a subgraph isomorphic to $F$ is expressible by a first-order sentence of quantifier depth $frac23,v(F)+1$, assuming that the host graph is sufficiently large and connected. On the other hand, this is impossible for any $F$ with using less than $frac23,v(F)-2$ first-order variables.
Changs lemma (Duke Mathematical Journal, 2002) is a classical result with applications across several areas in mathematics and computer science. For a Boolean function $f$ that takes values in {-1,1} let $r(f)$ denote its Fourier rank. For each positive threshold $t$, Changs lemma provides a lower bound on $wt(f):=Pr[f(x)=-1]$ in terms of the dimension of the span of its characters with Fourier coefficients of magnitude at least $1/t$. We examine the tightness of Changs lemma w.r.t. the following three natural settings of the threshold: - the Fourier sparsity of $f$, denoted $k(f)$, - the Fourier max-supp-entropy of $f$, denoted $k(f)$, defined to be $max {1/|hat{f}(S)| : hat{f}(S) eq 0}$, - the Fourier max-rank-entropy of $f$, denoted $k(f)$, defined to be the minimum $t$ such that characters whose Fourier coefficients are at least $1/t$ in absolute value span a space of dimension $r(f)$. We prove new lower bounds on $wt(f)$ in terms of these measures. One of our lower bounds subsumes and refines the previously best known upper bound on $r(f)$ in terms of $k(f)$ by Sanyal (ToC, 2019). Another lower bound is based on our improvement of a bound by Chattopadhyay, Hatami, Lovett and Tal (ITCS, 2019) on the sum of the absolute values of the level-$1$ Fourier coefficients. We also show that Changs lemma for the these choices of the threshold is asymptotically outperformed by our bounds for most settings of the parameters involved. Next, we show that our bounds are tight for a wide range of the parameters involved, by constructing functions (which are modifications of the Addressing function) witnessing their tightness. Finally we construct Boolean functions $f$ for which - our lower bounds asymptotically match $wt(f)$, and - for any choice of the threshold $t$, the lower bound obtained from Changs lemma is asymptotically smaller than $wt(f)$.
We study the communication complexity of linear algebraic problems over finite fields in the multi-player message passing model, proving a number of tight lower bounds. Specifically, for a matrix which is distributed among a number of players, we consider the problem of determining its rank, of computing entries in its inverse, and of solving linear equations. We also consider related problems such as computing the generalized inner product of vectors held on different servers. We give a general framework for reducing these multi-player problems to their two-player counterparts, showing that the randomized $s$-player communication complexity of these problems is at least $s$ times the randomized two-player communication complexity. Provided the problem has a certain amount of algebraic symmetry, which we formally define, we can show the hardest input distribution is a symmetric distribution, and therefore apply a recent multi-player lower bound technique of Phillips et al. Further, we give new two-player lower bounds for a number of these problems. In particular, our optimal lower bound for the two-player version of the matrix rank problem resolves an open question of Sun and Wang. A common feature of our lower bounds is that they apply even to the special threshold promise
In this paper, we prove topology dependent bounds on the number of rounds needed to compute Functional Aggregate Queries (FAQs) studied by Abo Khamis et al. [PODS 2016] in a synchronous distributed network under the model considered by Chattopadhyay et al. [FOCS 2014, SODA 2017]. Unlike the recent work on computing database queries in the Massively Parallel Computation model, in the model of Chattopadhyay et al., nodes can communicate only via private point-to-point channels and we are interested in bounds that work over an {em arbitrary} communication topology. This is the first work to consider more practically motivated problems in this distributed model. For the sake of exposition, we focus on two special problems in this paper: Boolean Conjunctive Query (BCQ) and computing variable/factor marginals in Probabilistic Graphical Models (PGMs). We obtain tight bounds on the number of rounds needed to compute such queries as long as the underlying hypergraph of the query is $O(1)$-degenerate and has $O(1)$-arity. In particular, the $O(1)$-degeneracy condition covers most well-studied queries that are efficiently computable in the centralized computation model like queries with constant treewidth. These tight bounds depend on a new notion of `width (namely internal-node-width) for Generalized Hypertree Decompositions (GHDs) of acyclic hypergraphs, which minimizes the number of internal nodes in a sub-class of GHDs. To the best of our knowledge, this width has not been studied explicitly in the theoretical database literature. Finally, we consider the problem of computing the product of a vector with a chain of matrices and prove tight bounds on its round complexity (over the finite field of two elements) using a novel min-entropy based argument.
In $(k,r)$-Center we are given a (possibly edge-weighted) graph and are asked to select at most $k$ vertices (centers), so that all other vertices are at distance at most $r$ from a center. In this paper we provide a number of tight fine-grained bounds on the complexity of this problem with respect to various standard graph parameters. Specifically: - For any $rge 1$, we show an algorithm that solves the problem in $O^*((3r+1)^{textrm{cw}})$ time, where $textrm{cw}$ is the clique-width of the input graph, as well as a tight SETH lower bound matching this algorithms performance. As a corollary, for $r=1$, this closes the gap that previously existed on the complexity of Dominating Set parameterized by $textrm{cw}$. - We strengthen previously known FPT lower bounds, by showing that $(k,r)$-Center is W[1]-hard parameterized by the input graphs vertex cover (if edge weights are allowed), or feedback vertex set, even if $k$ is an additional parameter. Our reductions imply tight ETH-based lower bounds. Finally, we devise an algorithm parameterized by vertex cover for unweighted graphs. - We show that the complexity of the problem parameterized by tree-depth is $2^{Theta(textrm{td}^2)}$ by showing an algorithm of this complexity and a tight ETH-based lower bound. We complement these mostly negative results by providing FPT approximation schemes parameterized by clique-width or treewidth which work efficiently independently of the values of $k,r$. In particular, we give algorithms which, for any $epsilon>0$, run in time $O^*((textrm{tw}/epsilon)^{O(textrm{tw})})$, $O^*((textrm{cw}/epsilon)^{O(textrm{cw})})$ and return a $(k,(1+epsilon)r)$-center, if a $(k,r)$-center exists, thus circumventing the problems W-hardness.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
