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]. Our algorithms are designed and analyzed in a new model of learning graphs that we call extended learning graphs. In addition, we present a framework in order to easily combine and analyze them. As a consequence we get much simpler algorithms and analyses than previous algorithms of Le Gall et al based on the MNRS quantum walk framework [SICOMP’11]. This is a joint work with Titouan Carette and Frédéric Magniez.