Computer Science/Discrete Mathematics Seminar II | |

Topic: | Average-case lower bounds for formula size |

Speaker: | Ran Raz |

Affiliation: | Weizmann Institute of Science; Visiting Professor, School of Mathematics |

Date: | Tuesday, March 17 |

Time/Room: | 10:30am - 12:30pm/S-101 |

We give an explicit example for a Boolean function $f : \{0,1\}^n \to \{0,1\}$, such that every Boolean formula of size at most $n^{2.999}$, with gates AND, OR and NOT, computes $f$ correctly on at most $1/2 + \epsilon$ fraction of the inputs, where $\epsilon$ is exponentially small. Joint work with Ilan Komargodski and Avishay Tal.