1. (Communication complexity) We exhibit a Boolean function f with discrepancy \Omega(1/n^4) under every product distribution but O(\sqrt n /2^{n/4}) under a certain non-product distribution. This partially solves an open problem of Kushilevitz and Nisan [25].

2. (Complexity of sign matrices) We construct a matrix A \in {-1,1}^N?N^logN with dimension complexity logN but margin complexity \Omega(N^{1/4}/ \sqrt {log N}). This gap is an exponential improvement over previous work. As an application to circuit complexity, we prove an \Omega(2^{n/4}/(d\sqrt n)) circuit lower bound for computing halfspaces by a majority of an arbitrary set of d gates. This complements a result of Goldmann, Hastad, and Razborov [15]. In addition, we prove new results on the complexity measures of sign matrices, complementing recent work by Linial et al. [27-29].

3. (Learning theory) We give a short and simple proof that the statistical-query (SQ) dimension of halfspaces in n dimensions is less than 2(n+1)^2 under all distributions (with n+1 being a trivial lower bound). This improves on the n^O(1) estimate from the fundamental paper of Blum et al. [5].

Finally, we motivate our learning-theoretic result for the complexity community by showing that SQ dimension estimates for natural classes of Boolean functions can resolve major open problems in complexity theory. Specifically, we show that an exp(2^(logn)^o(1) ) upper bound on the SQ dimension of AC^0 would imply an explicit language in PSPACE^cc \PH^cc.