Abstract: In a coordination problem, users in a network observing correlated inputs collaborate to evaluate possibly randomized functions of the inputs.

Given a boolean function $f : \{0, 1\}^n \rightarrow \{0, 1\}$ define the function $f \circ \mathsf{XOR}$ on $2n$ bits by $f \circ \mathsf{XOR} (x_1, \dots, x_n, y_1, \dots, y_n) = f(x_1 \oplus y_1, \dots, x_n \oplus y_n)$.  Such a function is cal

In the first part, we will consider the connection between two well-known complexity measures --- communication complexity and query complexity.

Boolean functions are central to computer science. This presentation will focus on Boolean functions from the perspective of certain measures of complexity.

Abstract: High dimensional problems are ubiquitous in machine learning and many other fields such as biology, finance, environmental science, medicine, etc.