We study the correlation between low-degree GF(2) polynomials p and explicit functions. Our main results are the following:

(I) We prove that the Mod_m unction on n bits has correlation at most exp(-Omega(n/4^d)) with any GF(2) polynomial of degree d, for any fixed odd integer m. This improves on the ... more >>>

Let m,q > 1 be two integers that are co-prime and A be any subset of Z_m. Let P be any multi-linear polynomial of degree d in n variables over Z_m. We show that the MOD_q boolean function on n variables has correlation at most exp(-\Omega(n/(m2^{m-1})^d)) with the boolean function ... more >>>

We examine the communication required for generating random variables
remotely. One party Alice will be given a distribution D, and she
has to send a message to Bob, who is then required to generate a
value with distribution exactly D. Alice and Bob are allowed
to share random bits generated ... more >>>

We develop a new technique of proving lower bounds for the randomized communication complexity of boolean functions in the multiparty 'Number on the Forehead' model. Our method is based on the notion of voting polynomial degree of functions and extends the Degree-Discrepancy Lemma in the recent work of Sherstov (STOC'07). ... more >>>

We report on some initial results of a brute-force search for determining the maximum correlation between degree-$d$ polynomials modulo $p$ and the $n$-bit mod $q$ function. For various settings of the parameters $n,d,p,$ and $q$, our results indicate that symmetric polynomials yield the maximum correlation. This contrasts with the previously-analyzed ... more >>>