Sublinear-Time Algorithms for Max Cut and Unique Label Cover on Expanders (Pan Peng)


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.


2022-08-23  13:30 - 14:30   


Pan Peng,  University of Science and Technology of China


Tencent meeting ID: 853-8759-9058; PW: 123456