**Title: Settling the complexity of k-disjointness and the k-Hamming distance problems**

**Advisor: **Shayan Oveis Gharan

**Supervisory Committee: **Shayan Oveis Gharan (Chair), Ioana Dumitriu (GSR, Math), Thomas Rothvoss, Anup Rao, and Paul Beame

**Abstract: **Suppose two parties, traditionally called Alice and Bob, are given respectively the inputs and to a function and are required to compute . Since each party only has one part of the input, they can compute only if some communication takes place between them. The communication complexity of a given function is the minimum amount of communication (in bits) needed to evaluate it on any input with high probability.

We study the communication complexity of two related problems, the -Hamming distance and -disjointness and give tight bounds to both of these problems: The -round communication complexity of the -disjointness problem is , whereas a tight bound holds for the -Hamming distance problem for any number of rounds.

The lower bound direction of our first result is obtained by proving a *super-sum* result on computing the OR of equality problems, which is the first of its kind. Using our second bound, we settle the complexity of various property testing problems such as -linearity, which was open since 2002 or earlier. Our lower bounds are obtained via information theoretic arguments and along the way we resolve a question conjectured by ErdÅ‘s and Simonovits in 1982, which incidentally was studied even earlier by Blakley and Dixon in 1966.