יום ראשון, 13.1.2008, 11:00
חדר 337, בניין טאוב למדעי המחשב
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.