COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > CQIF Seminar > Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision

## Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph CollisionAdd to your list(s) Download to your calendar using vCal - Robin Kothari (IQC)
- Thursday 05 July 2012, 12:00-13:00
- MR14, Centre for Mathematical Sciences.
If you have a question about this talk, please contact Ashley Montanaro. Note change of time and room The quantum query complexity of Boolean matrix multiplication is typically studied as a function of the matrix dimension, n, as well as 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 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 our algorithm is essentially tight. We first reduce Boolean 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. This talk is part of the CQIF Seminar series. ## This talk is included in these lists:- All CMS events
- CMS Events
- CQIF Seminar
- DAMTP info aggregator
- Hanchen DaDaDash
- Interested Talks
- MR14, Centre for Mathematical Sciences
- bld31
Note that ex-directory lists are not shown. |
## Other listsTracing Human Ancestry, using DNA Statistics of Prof Philip Dawid## Other talksA rose by any other name Gaze and Locomotion in Natural Terrains On the elastic-brittle versus ductile fracture of lattice materials What is the Market Potential of Multilingualism? CANCELLED Ñande reko: alterity and (non-)participatory research with guaraní women in Bolivia Large Scale Ubiquitous Data Sources for Crime Prediction Single Cell Seminars (November) Cambridge - Corporate Finance Theory Symposium September 2017 - Day 1 Validation & testing of novel therapeutic targets to treat osteosarcoma Lunchtime Talk: Helen's Bedroom Sneks long balus Atmospheric Structure Revealed by Refraction of Routine Radio Transmissions from Civil Aircraft. |