Haifa University - Dept. of CS Theory Seminar
Speaker : Amir Yehudayoff, Weizmann.
Title: "Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors".
Date: Thursday, Feb. 28.
Place: Haifa U. Education Building, room 570.
Time: 12:15 - 13:30
Abstract:
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.