BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Improving Quantum Query Complexity of Boolean Matrix Multiplicatio
 n Using Graph Collision - Robin Kothari (IQC)
DTSTART:20120705T110000Z
DTEND:20120705T120000Z
UID:TALK38596@talks.cam.ac.uk
CONTACT:Ashley Montanaro
DESCRIPTION:The quantum query complexity of Boolean matrix multiplication 
 is typically studied as a function of the matrix dimension\, n\, as well a
 s the number of 1s in the output\, l. We prove an upper bound of O(n sqrt(
 l)) for all values of l. This is an improvement over previous algorithms f
 or all values of l. On the other hand\, we show that for any eps < 1 and a
 ny l <= eps n^2\, there is an Omega(n sqrt(l)) lower bound for this proble
 m\, showing that our algorithm is essentially tight.\nWe first reduce Bool
 ean matrix multiplication to several instances of graph collision. We then
  provide an algorithm that takes advantage of the fact that the underlying
  graph in all of our instances is very dense to find all graph collisions 
 efficiently. 
LOCATION:MR14\, Centre for Mathematical Sciences
END:VEVENT
END:VCALENDAR