Seminar: Mathieu Lauriere
Extended Learning Graphs for Triangle Finding
Mathieu Lauriere, New York University, Shanghai
In this talk we present new quantum algorithms for Triangle Finding improving its best previously known quantum query complexities for both dense and spare instances. For dense graphs on n vertices, we get a query complexity of O(n^{5/4}) without any of the extra logarithmic factors present in the previous algorithm of Le Gall [FOCS’14]. For sparse graphs we also improve some of the results obtained by Le Gall and Nakajima [ISAAC’15].