Department of Mathematics - Master Calendar

Speaker: Asaf Ferber (UC Irvine)

Title: Quantum Algorithms on Graphs

Abstract: In this talk, I will provide a brief introduction to quantum computation and demonstrate its potential for accelerating classical graph algorithms. Specifically, I will present an asymptotically tight result for learning a Hamiltonian cycle using OR queries, as well as a significant polynomial improvement on the best-known quantum algorithm for (Δ+1)-coloring a graph with maximum degree Δ.

This work is based on joint research with Liam Hardiman (UCI) and Xiaonan Chen (UCI).