正则扩展图

论文主要针对三类实例证明了加速效果：含大量偏置变量的公式、半随机2-CNF公式、正则扩展图上的Max-Cut和随机块模型图。

论文将算法应用于正则扩展图和随机块模型生成的图上的Max-Cut问题，同样获得了指数级加速。

正则扩展图是一类具有强连通性质的稀疏图，其中每个顶点的度数相同，且图的边扩展性很好。