Academic literature on the topic 'Round Complexity'

Motivated by the increasing need to understand the distributed algorithmic foundations of large-scale graph computations, we study some fundamental graph problems in a message-passing model for distributed computing where k ≥ 2 machines jointly perform computations on graphs with n nodes (typically, n >> k). The input graph is assumed to be initially randomly partitioned among the k machines, a common implementation in many real-world systems. Communication is point-to-point, and the goal is to minimize the number of communication rounds of the computation. Our main contribution is the General Lower Bound Theorem , a theorem that can be used to show non-trivial lower bounds on the round complexity of distributed large-scale data computations. This result is established via an information-theoretic approach that relates the round complexity to the minimal amount of information required by machines to solve the problem. Our approach is generic, and this theorem can be used in a “cookbook” fashion to show distributed lower bounds for several problems, including non-graph problems. We present two applications by showing (almost) tight lower bounds on the round complexity of two fundamental graph problems, namely, PageRank computation and triangle enumeration . These applications show that our approach can yield lower bounds for problems where the application of communication complexity techniques seems not obvious or gives weak bounds, including and especially under a stochastic partition of the input. We then present distributed algorithms for PageRank and triangle enumeration with a round complexity that (almost) matches the respective lower bounds; these algorithms exhibit a round complexity that scales superlinearly in k , improving significantly over previous results [Klauck et al., SODA 2015]. Specifically, we show the following results: PageRank: We show a lower bound of Ὼ(n/k 2 ) rounds and present a distributed algorithm that computes an approximation of the PageRank of all the nodes of a graph in Õ(n/k 2 ) rounds. Triangle enumeration: We show that there exist graphs with m edges where any distributed algorithm requires Ὼ(m/k 5/3 ) rounds. This result also implies the first non-trivial lower bound of Ὼ(n 1/3 ) rounds for the congested clique model, which is tight up to logarithmic factors. We then present a distributed algorithm that enumerates all the triangles of a graph in Õ(m/k 5/3 + n/k 4/3 ) rounds.

In this paper, a new method for constructing a Mixed Integer Linear Programming (MILP) model on conditional differential cryptanalysis of the nonlinear feedback shift register- (NLFSR-) based block ciphers is proposed, and an approach to detecting the bit with a strongly biased difference is provided. The model is successfully applied to the block cipher KATAN32 in the single-key scenario, resulting in practical key-recovery attacks covering more rounds than the previous. In particular, we present two distinguishers for 79 and 81 out of 254 rounds of KATAN32. Based on the 81-round distinguisher, we recover 11 equivalent key bits of 98-round KATAN32 and 13 equivalent key bits of 99-round KATAN32. The time complexity is less than 2 31 encryptions of 98-round KATAN32 and less than 2 33 encryptions of 99-round KATAN32, respectively. Thus far, our results are the best known practical key-recovery attacks for the round-reduced variants of KATAN32 regarding the number of rounds and the time complexity. All the results are verified experimentally.

Given \( x,y\in \lbrace 0,1\rbrace ^n \) , Set Disjointness consists in deciding whether \( x_i=y_i=1 \) for some index \( i \in [n] \) . We study the problem of computing this function in a distributed computing scenario in which the inputs \( x \) and \( y \) are given to the processors at the two extremities of a path of length \( d \) . Each vertex of the path has a quantum processor that can communicate with each of its neighbours by exchanging \( \operatorname{O}(\log n) \) qubits per round. We are interested in the number of rounds required for computing Set Disjointness with constant probability bounded away from \( 1/2 \) . We call this problem “Set Disjointness on a Line”. Set Disjointness on a Line was introduced by Le Gall and Magniez [ 14 ] for proving lower bounds on the quantum distributed complexity of computing the diameter of an arbitrary network in the CONGEST model. However, they were only able to provide a lower bound when the local memory used by the processors on the intermediate vertices of the path is severely limited. More precisely, their bound applies only when the local memory of each intermediate processor consists of \( \operatorname{O}(\log n) \) qubits. In this work, we prove an unconditional lower bound of \( \widetilde{\Omega }\big (\sqrt [3]{n d^2}+\sqrt {n} \, \big) \) rounds for Set Disjointness on a Line with \( d + 1 \) processors. This is the first non-trivial lower bound when there is no restriction on the memory used by the processors. The result gives us a new lower bound of \( \widetilde{\Omega } \big (\sqrt [3]{n\delta ^2}+\sqrt {n} \, \big) \) on the number of rounds required for computing the diameter \( \delta \) of any \( n \) -node network with quantum messages of size \( \operatorname{O}(\log n) \) in the CONGEST model. We draw a connection between the distributed computing scenario above and a new model of query complexity. In this model, an algorithm computing a bi-variate function \( f \) (such as Set Disjointness) has access to the inputs \( x \) and \( y \) through two separate oracles \( {\mathcal {O}}_x \) and \( {\mathcal {O}}_y \) , respectively. The restriction is that the algorithm is required to alternately make \( d \) queries to \( {\mathcal {O}}_x \) and \( d \) queries to \( {\mathcal {O}}_y \) , with input-independent computation in between queries. The model reflects a “switching delay” of \( d \) queries between a “round” of queries to \( x \) and the following “round” of queries to \( y \) . The information-theoretic technique we use for deriving the round lower bound for Set Disjointness on a Line also applies to the number of rounds in this query model. We provide an algorithm for Set Disjointness in this query model with round complexity that matches the round lower bound stated above, up to a polylogarithmic factor. This presents a barrier for obtaining a better round lower bound for Set Disjointness on the Line. At the same time, it hints at the possibility of better communication protocols for the problem.