Speaker: Miklos Santha CNRS,Université Paris Diderot & CQT, Singapore
Time: 2012-07-05 14:30-2012-07-05 15:30
Venue: FIT 1-222
Download: Click!
Abstract:
We show that the quantum query complexity of detecting if an n-vertex graph contains a triangle is O(n^{9/7}). This improves the previous best algorithm making O(n^{35/27}) queries. For the problem of determining if a binary operation on a set of size n is associative, we give an algorithm making O(n^{10/7}) queries, the first improvement to the trivial O(n^{3/2}) application of Grover search.
Our algorithms are designed using the learning graph framework of Belovs. This recently introduced model of computing can be viewed as the minimization form of the general adversary bound with additional structure imposed on the form of the solution.
In the talk, before explaining the new algorithms, I will give a detailed introduction to the learning graph model. The talk is self contained, and it doesn't require any previous knowledge about quantum computing.
This is joint work with Troy Lee and Frédéric Magniez.
Short Bio:
Miklos Santha received his MS degree in mathematics from the Eötvös Loránd University in Budapest, and his PhD in Computer Science from the Université Paris 7. Since 1988 he has been with the Centre National de la Recherche Scientifique where he is currently Senior Researcher at the Université Paris Diderot. Since 2008 he has been also Principal Investigator in the Centre for Quantum Technologies at the National University of Singapore. His research interests include complexity theory, randomized and quantum computing.
