Boolean functions capture various problems and situations arising in computer science and other areas. In this synopsis, we study boolean functions using two complexity measures.

We study the question of constructing _hitting sets_ for polynomials computed by several algebraic models.

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.