Speaker: |
Deeparnab Chakrabarty (Microsoft Research, India #9, Lavelle Road Bangalore, Karnataka 560025 ) |

Organiser: |
Prahladh Harsha |

Date: |
Thursday, 2 May 2013, 15:30 to 16:30 |

Venue: |
AG-80 |

(Scan to add to calendar)

One of the main ingredients will be an isoperimetry result on the *directed* hypercube, where the edges of the hypercube are directed from $y$ to $x$ if $x > y$. In particular, we show that the support set (the $x$'s s.t. $f(x)=1$) of a $\epsilon$-far from monotone function, either have a large directed edge expansion, or a large directed vertex expansion (joint work with C. Seshadhri).