Theory Lunch Seminar

Wednesday, February 15, 2017 -
12:00pm to 1:00pm

Location:

Reddy Conference Room 4405 Gates Hillman Center

Speaker:

SHALEV BEN-DAVID, Ph.D. Student http://toc.csail.mit.edu/user/127

Event Website:

http://www.cs.cmu.edu/~theorylunch/20170215.html

For More Information, Contact:

nbendavi@cs.cmu.edu

I will explain the cheat sheet technique in query complexity, and show how to use it to get a power 2.5 separation between classical and quantum computation (beating the quadratic speedup of Grover search). I'll then discuss the connections between query and communication complexity, and present recent applications of the cheat sheet technique in the communication complexity setting.—Shalev Ben-David is a PhD student in his last year at MIT.Supported in part by the Simons FoundationVideo recording

Keywords:

Seminar Series