In this paper we study multilinear formulas, monotone arithmetic circuits, maximal partition
discrepancy, best partition communication complexity and mixed two source extractors.
We will first define maximal partition discrepancy, and construct a function f that has
exponentially small maximal partition discrepancy. We will then review several application
of this construction:
1. The best partition communication complexity of f is \Theta(n).
2. It can be used to extract a linear number of almost perfect random bits from a mixed two
source of randomness.
3. We use f to prove lower bounds for several models of arithmetic circuits;
for example, monotone arithmetic circuits and orthogonal multilinear formulas.
We will focus mainly on the monotone model.
Joint work with Ran Raz.