## Regularity Lemmas and Other Extremal Results

Guy Moshkovitz

Member, School of Mathematics

October 1, 2018

Guy Moshkovitz

Member, School of Mathematics

October 1, 2018

Dor Minzer

Tel Aviv University; Member, School of Mathematics

October 1, 2018

Marco Méndez Guaraco

University of Chicago; Member, School of Mathematics

October 1, 2018

Jacob Matherne

Member, School of Mathematics

October 1, 2018

Ángel Martínez Martínez

Universidad Autónoma de Madrid; Member, School of Mathematics

October 1, 2018

Avishay Tal

University of California, Berkeley

October 1, 2018

In their seminal paper, Bennett, Bernstein, Brassard and Vazirani [SICOMP, 1997] showed that relative to an oracle, quantum algorithms are unable to solve NP-complete problems in sub-exponential time (i.e., that Grover's search is optimal in this setting).