Let $G$ be a finite group given as input by its multiplication table. For a subset $S$ of $G$ and an element $g\in G$ the Cayley Group Membership Problem (denoted CGM) is to check if $g$ belongs to the subgroup generated by $S$. While this problem is easily seen to be in polynomial time, pinpointing its parallel complexity has been of research interest over the years. In this paper we further explore the parallel complexity of the abelian CGM problem, with focus on the dynamic setting: the generating set $S$ changes with insertions and deletions and the goal is to maintain a data structure that supports efficient membership queries to the subgroup $\angle{S}$. We obtain the following results: 1. We first consider the more general problem of Monoid Membership. When $G$ is a commutative monoid we give a deterministic dynamic algorithm constant time parallel algorithm for membership testing that supports $O(1)$ insertions and deletions in each step. 2. Building on the previous result we show that there is a dynamic randomized constant-time parallel algorithm for abelian CGM that supports polylogarithmically many insertions/deletions to $S$ in each step. 3. If the number of insertions/deletions is at most $O(\log n/\log\log n)$ then we obtain a deterministic dynamic constant-time parallel algorithm for the problem. 4. We obtain analogous results for the dynamic abelian Group Isomorphism.

We study distribution testing in the standard access model and the conditional access model when the memory available to the testing algorithm is bounded. In both scenarios, the samples appear in an online fashion and the goal is to test the properties of distribution using an optimal number of samples subject to a memory constraint on how many samples can be stored at a given time. First, we provide a trade-off between the sample complexity and the space complexity for testing identity when the samples are drawn according to the conditional access oracle. We then show that we can learn a succinct representation of a monotone distribution efficiently with a memory constraint on the number of samples that are stored that is almost optimal. We also show that the algorithm for monotone distributions can be extended to a larger class of decomposable distributions.

Distribution testing deals with what information can be deduced about an unknown distribution over $$\{1,\ldots ,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,\ldots ,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,\ldots ,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,\ldots ,n\}$$ .

We consider one-sided error property testing of $\mathcal{F}$-minor freeness in bounded-degree graphs for any finite family of graphs $\mathcal{F}$ that contains a minor of $K_{2,k}$, the $k$-circus graph, or the $(k\times 2)$-grid for any $k\in\mathbb{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 $\tilde{O}(n^{2/3} / ε^5)$. Czumaj et~al.\ showed that cycle-freeness and $C_k$-minor freeness can be tested with query complexity $\tilde{O}(\sqrt{n})$ by using random walks, and that testing $H$-minor freeness for any $H$ that contains a cycles requires $Ω(\sqrt{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.

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) / (epsilon Phi^2)) in the CONGEST model, which accepts graphs with conductance Phi and rejects graphs that are epsilon-far from having conductance at least Phi^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 Omega(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.

Let $G =\langle S\rangle$ be a solvable permutation group given as input by the generating set $S$, that is, $G$ is a solvable subgroup of the symmetric group $S_n$. We give a deterministic polynomial-time algorithm that computes an expanding generating set $T$ of size $\tilde{O}(n^2(1/\lambda)^{c})$ for $G$ such that the undirected Cayley graph ${\rm Cay}_u(G,T)$ is a $\lambda$-spectral expander and the constant $c$ is at most $8$ (the $\tilde{O}$ notation suppresses $\log ^{O(1)}n$ and $\log ^{O(1)}(1/\lambda)$ factors). As a byproduct of our proof, we get a new explicit construction of $\varepsilon$-bias spaces of size $\tilde{O}(n (\log d)^{O(1)}(1/\varepsilon)^{c})$ for the groups $\mathbb{Z}_d^n$ and $c\leq 8$. The earlier known size bound was $O((d + n/\varepsilon^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\le S_n$ given by a generating set, in deterministic polynomial time we can compute an expanding generating set $T$ of size $\left({n}/{\lambda}\right)^{O(1)}$ such that ${\rm Cay}_u(G,T)$ is a $\lambda$-spectral expander where the $O(1)$ notation involves a large constant.

We show that every non-adaptive property testing algorithm making a constant number of queries, over a fixed alphabet, can be converted to a sample-based (as per [Gold Reich and Ron, 2015]) testing algorithm whose average number of queries is a fixed, smaller than 1, power of n. Since the query distribution of the sample-based algorithm is not dependent at all on the property, or the original algorithm, this has many implications in scenarios where there are many properties that need to be tested for concurrently, such as testing (relatively large) unions of properties, or converting a Merlin-Arthur Proximity proof (as per [Gur and Rothblum, 2013]) to a proper testing algorithm. The proof method involves preparing the original testing algorithm for a combinatorial analysis. For the analysis we develop a structural lemma for hyper graphs that may be of independent interest. When analyzing a hyper graph that was extracted from a 2-sided test, it allows for finding generalized sunflowers that provide for a large-deviation type analysis. For 1-sided tests the bounds can be improved further by applying Janson's inequality directly over our structures.