דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extra
event speaker icon
אמיר יהודיוף
event date icon
יום ראשון, 13.1.2008, 11:00
event location icon
חדר 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.
[בחזרה לאינדקס האירועים]