Abstract
We give the first sublinear-time algorithm for the Max Cut problem with non-trivial approximation guarantee for a natural class of graphs, i.e., expander graphs. Given query access to the adjacency list of such a graph with edges and conductance at least , our algorithm runs in time and provides a -approximation to , the maximum fraction of the edges cut by a bipartition of . We also give a sublinear-time algorithm for the Unique Label Cover (also known as Unique Games) problem on expanders in the bounded-degree model. Previously, it was only known that the latter problem can be solved in polynomial time by using semidefinite programming. In contrast, our algorithms and analysis are based on spectral, random walk, and property testing techniques.
Joint work with Yuichi Yoshida.
Time
2022-08-23 13:30 - 14:30
Speaker
Pan Peng, University of Science and Technology of China
Room
Tencent meeting ID: 853-8759-9058; PW: 123456