The Taub Faculty of Computer Science Events and Talks

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.