Speaker: |
Anamay Tengse |

Organiser: |
Sayantan Chakraborty |

Date: |
Friday, 20 Apr 2018, 17:15 to 18:15 |

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

(Scan to add to calendar)

We will see an exp$(n)$ lower bound against this model for the {\em monomial} $x_1 x_2 \cdots x_n$, and also an almost matching upper bound using {\em Fischer's trick}. We will then extend the ideas in the lower bound to obtain an $n^{O(\log n)}$ sized hitting set (Forbes-Shpilka '13).

Depending on the time left, we will sketch an $n^{O(\log \log n)}$ sized hitting set construction (Forbes-Shpilka-Saptharishi '14).