In this talk I will describe some recent work on distributed property testing in the CONGEST model: we have a network of computing nodes that communicate over some unknown network graph where the communication links have bounded bandwidth. The nodes wish to solve some global task, such as determining whether the network graph satisfies some property (e.g., whether it is bipartite), or computing some function of their inputs. Our goal is to solve the problem in a small number of communication rounds, overcoming the fact that the nodes can typically only "see" or learn a small part of the network. Lower bounds for this model are typically shown using connections to communication complexity.

In the talk we will focus on two problems: subgraph-freeness and uniformity testing. In the subgraph-freeness problem, we wish to check whether the network graph contains a copy of some fixed constant-sized subgraph H; this problem has received significant attention recently, and efficient algorithms are known for some specific subgraphs, but many questions remain open, even in the exact (non-property testing) case.

In the uniformity-testing problem, each network node receives a small number of samples from some unknown distribution mu, and our goal is to check whether mu is the uniform distribution or whether it is far from uniform (in L1 distance). I will describe recent upper and lower bounds on the problem.