Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extra
event speaker icon
Amir Yehudayoff
event date icon
Sunday, 13.01.2008, 11:00
event location icon
Room 337-8 Taub Bld.
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.