BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:CQIF Seminar
SUMMARY:Improving Quantum Query Complexity of Boolean Matr
ix Multiplication Using Graph Collision - Robin Ko
thari (IQC)
DTSTART;TZID=Europe/London:20120705T120000
DTEND;TZID=Europe/London:20120705T130000
UID:TALK38596AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/38596
DESCRIPTION:The quantum query complexity of Boolean matrix mul
tiplication is typically studied as a function of
the matrix dimension\, n\, as well as the number o
f 1s in the output\, l. We prove an upper bound of
O(n sqrt(l)) for all values of l. This is an impr
ovement over previous algorithms for all values of
l. On the other hand\, we show that for any eps <
1 and any l <= eps n^2\, there is an Omega(n sqrt
(l)) lower bound for this problem\, showing that o
ur algorithm is essentially tight.\nWe first reduc
e Boolean matrix multiplication to several instanc
es of graph collision. We then provide an algorith
m that takes advantage of the fact that the underl
ying graph in all of our instances is very dense t
o find all graph collisions efficiently.
LOCATION:MR14\, Centre for Mathematical Sciences
CONTACT:Ashley Montanaro
END:VEVENT
END:VCALENDAR