BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260708T214911Z
UID:Seminar-dept-1503@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20260721T130000
DTEND:20260721T140000
SUMMARY:School Seminar Series
DESCRIPTION:Amin Shiraz Gilani:  Quantum Algorithms on Edge Lists Hiding, Shuffling, and Cycle Finding\n\nThe edge list model is arguably the simplest input model for graphs, where the graph is specified by a list of its edges. In this model, we study the quantum query complexity of three variants of the triangle finding problem. The first asks whether there exists a triangle containing a target edge and raises general questions about the hiding of a problem’s input among irrelevant data. The second asks whether there exists a triangle containing a target vertex and raises general questions about the shuffling of a problem’s input. The third asks whether there exists a triangle; this problem bridges the 3-distinctness and 3-sum problems, which have been extensively studied by both cryptographers and complexity theorists. We provide tight or nearly tight results for these problems as well as some first answers to the general questions they raise. Furthermore, given any graph with low maximum degree, such as a typical random sparse graph, we prove that the quantum query complexity of finding a length-k cycle in its length-m edge list is m^{3/4−1/(2k+2−4)±o(1)}, which matches the quantum query complexity of k-distinctness on length-m inputs up to an m^{o(1)} factor. We prove the lower bound by developing new techniques within Zhandry’s recording query framework [Zha19] as generalized by Hamoudi and Magniez [HM23]. These techniques extend the framework to treat any non-product distribution that results from conditioning a product distribution on the absence of rare events. We prove the upper bound by adapting Belovs’s learning graph algorithm for k-distinctness [Bel12b].\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1503
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR