Speaker: |
Irit Dinur (Weizmann Institute of Science Department of Applied Math and Computer Science Rehovot 76100 Israel) |

Organiser: |
Piyush Srivastava |

Date: |
Tuesday, 5 Dec 2017, 11:30 to 12:30 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

We study the same question on the p-biased hypercube, for very small $p$. The $p$-biased hypercube is a product probability space in which each coordinate is 1 with probability p and 0 otherwise. In this space most of the measure is on $n$-bit strings whose Hamming weight about $pn \ll n$.

It turns out that here new phenomena emerge. For example, the function $x_1 + ... + x_n=p (where x_i \in {0,1})$ is close to Boolean but not close to a junta.

We characterize low degree functions that are almost Boolean and show that they are close to a new class of functions which we call sparse juntas.

An interesting aspect of our proof is that it relies on a local to global agreement theorem. We cover the $p$-biased hypercube by many smaller dimensional copies of the uniform hypercube, and approximate our function locally via the Kindler-Safra theorem for constant p. We then stitch the local approximations together into one global function that is a sparse junta (based on joint work with Yuval Filmus and Prahladh Harsha).