Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture

Andris Ambainis, Harry Buhrman, Koen Leijnse +2

Classically, for many computational problems one can conclude time lower bounds conditioned on the hardness of one or more of key problems: k-SAT, 3SUM and APSP. More recently, sim…