Quantum Fine-Grained Complexity
Quantum Nano Centre (QNC) Room 0101, 200 University Avenue West, Waterloo, ON
IQC Colloquium, Harry Buhrman - QuSoft
One of the major challenges in computer science is to establish lower bounds on the resources, usually time, that are needed to solve computational problems. This holds in particular for computational problems that appear in practise. One way towards dealing with this situation is the study of fine- grained complexity where we use special reductions to prove time lower bounds for many diverse problems based on the conjectured hardness of some key problems.