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