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.