Vasudev Yadu

We study property testing in the distributed model and extend its setting from testing with one-sided error to testing with two-sided error. In particular, we develop a two-sided error property tester for general graphs with round complexity O(log(n)/(Φ2)) in the CONGEST model, which accepts graphs with conductance Φ and rejects graphs that are -far from having conductance at least Φ2/1000 with constant probability. Our main insight is that one can start poly(n) random walks from a few random vertices without violating the congestion and unite the results to obtain a consistent answer from all vertices. For connected graphs, this is even possible when the number of vertices is unknown. We also obtain a matching Ω(log n) lower bound for the LOCAL and CONGEST models by an indistinguishability argument. Although the power of vertex labels that arises from two-sided error might seem to be much stronger than in the sequential query model, we can show that this is not the case.

Distribution testing deals with what information can be deduced about an unknown distribution over { 1 , … , n} , where the algorithm is only allowed to obtain a relatively small number of independent samples from the distribution. In the extended conditional sampling model, the algorithm is also allowed to obtain samples from the restriction of the original distribution on subsets of { 1 , … , n}. In 2015, Canonne, Diakonikolas, Gouleakis and Rubinfeld unified several previous results, and showed that for any property of distributions satisfying a “decomposability” criterion, there exists an algorithm (in the basic model) that can distinguish with high probability distributions satisfying the property from distributions that are far from it in the variation distance. We present here a more efficient yet simpler algorithm for the basic model, as well as very efficient algorithms for the conditional model, which until now was not investigated under the umbrella of decomposable properties. Additionally, we provide an algorithm for the conditional model that handles a much larger class of properties. Our core mechanism is an algorithm for efficiently producing an interval-partition of { 1 , … , n} that satisfies a “fine-grain” quality. We show that with such a partition at hand we can avoid the search for the “correct” partition of { 1 , … , n}.

Dynamic Complexity was introduced by Immerman and Patnaik [25] (see also [14]). It has seen a resurgence of interest in the recent past, see [2, 4, 8–12, 24, 26, 30, 31] for some representative examples. Use of linear algebra has been a notable feature of some of these papers. We extend this theme to show that the gap version of spectral expansion in bounded degree graphs can be maintained in the class DynAC0 (also known as DynFO, for domain independent queries) under batch changes (insertions and deletions) of O(lognloglogn) many edges. The spectral graph theoretic material of this work is based on the paper by Kale-Seshadhri [23]. Our primary technical contribution is to maintain up to logarithmic powers of the transition matrix of a bounded degree undirected graph in DynAC0.

We consider one-sided error property testing of F-minor freeness in bounded-degree graphs for any finite family of graphs F that contains a minor of K2,k, the k-circus graph, or the (k × 2)-grid for any k ∈ N. This includes, for instance, testing whether a graph is outerplanar or a cactus graph. The query complexity of our algorithm in terms of the number of vertices in the graph, n, is O(n2/3/5). Czumaj et al. (2014) showed that cycle-freeness and Ck-minor freeness can be tested with query complexity O(n) by using random walks, and that testing H-minor freeness for any H that contains a cycles requires (n) queries. In contrast to these results, we analyze the structure of the graph and show that either we can find a subgraph of sublinear size that includes the forbidden minor H, or we can find a pair of disjoint subsets of vertices whose edge-cut is large, which induces an H-minor.

Let G = S be a solvable permutation group given as input by the generating set S, that is, G is a solvable subgroup of the symmetric group Sn. We give a deterministic polynomial-time algorithm that computes an expanding generating set T of size O(n2(1/λ)c) for G such that the undirected Cayley graph Cayu(G, T) is a λ-spectral expander and the constant c is at most 8 (the O notation suppresses logO(1) n and logO(1)(1/λ) factors). As a byproduct of our proof, we get a new explicit construction of ε-bias spaces of size O(n(log d)O(1)(1/ε)c) for the groups Znd and c ≤ 8. The earlier known size bound was O((d + n/ε2)11/2) given by [Y. Azar, R. Motwani, and J. Naor, Combinatorica, 18 (1998), pp. 151-171]. We also note that for any permutation group G ≤ Sn given by a generating set, in deterministic polynomial time we can compute an expanding generating set T of size (n/λ)O(1) such that Cayu(G, T) is a λ-spectral expander where the O(1) notation involves a large constant.

We initiate the study of distributed graph algorithms under the presence of Byzantine nodes. We consider the fundamental problem of testing the connectivity of a graph in the congested clique model in a Byzantine setting. We are given a n-vertex (arbitrary) graph G embedded in a n-node congested clique where an arbitrary subset of B nodes of the clique of size up to (1/3 - ε)n (for any arbitrary small constant ε > 0) can be Byzantine. We consider the full information model where Byzantine nodes can behave arbitrarily, collude with each other, and have unlimited computational power and full knowledge of the states and actions of the honest nodes, including random choices made up to the current round. Our main result is an efficient randomized distributed algorithm that is able to correctly distinguish between two contrasting cases: (1) the graph G \ B (i.e., the graph induced by the removal of the vertices assigned to the Byzantine nodes in the clique) is connected or (2) the graph G is far from connected, i.e., it has at least 2|B| + 1 connected components. Our algorithm runs in O(polylog n) rounds in the congested clique model and guarantees that all honest nodes will decide on the correct case with high probability. Since Byzantine nodes can lie about the vertices assigned to them, we show that this is essentially the best possible that can be done by any algorithm. Our result can be viewed also in the spirit of property testing, where our algorithm is able to distinguish between two contrasting cases while giving no guarantees if the graph falls in the grey area (i.e., neither of the cases occur). Our work is a step towards robust and secure distributed graph computation that can output meaningful results even in the presence of a large number of faulty or malicious nodes.