Computer Science/Discrete Mathematics Seminar I | |

Topic: | A nearly optimal lower bound on the approximate degree of AC$^0$ |

Speaker: | Mark Bun |

Affiliation: | Princeton University |

Date: | Monday, October 23 |

Time/Room: | 11:00am - 12:15pm/S-101 |

Video Link: | https://video.ias.edu/csdm/2017/1023-MarkBun |

The approximate degree of a Boolean function $f$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most $1/3$. For any constant $\delta > 0$, we exhibit an AC$^0$ function of approximate degree $\Omega(n^{1-\delta})$. This improves over the best previous lower bound of $\Omega(n^{2/3})$ due to Aaronson and Shi, and nearly matches the trivial upper bound of $n$ that holds for any function. Our lower bound follows from a new hardness amplification theorem, which shows how to increase the approximate degree of a given function while preserving its computability by constant-depth circuits. I will also describe several applications of our results in communication complexity and cryptography. This is joint work with Justin Thaler and is available at https://eccc.weizmann.ac.il/report/2017/051/.