论文标题
CSP的流媒体和草图复杂性：调查
Streaming and Sketching Complexity of CSPs: A survey
论文作者
论文摘要
在这项调查中，我们描述了过去十年左右的进步，以理解求解约束满意度问题（CSP）的复杂性（CSP）大约在计算的流和草图模型中。在调查了一些结果之后，我们给出了一些证明的草图，特别是试图解释为什么要绘制在多项式空间制度中工作的算法有严格的二分法结果。
In this survey we describe progress over the last decade or so in understanding the complexity of solving constraint satisfaction problems (CSPs) approximately in the streaming and sketching models of computation. After surveying some of the results we give some sketches of the proofs and in particular try to explain why there is a tight dichotomy result for sketching algorithms working in subpolynomial space regime.
