In this column, we overview recent progress by many authors on understanding the approximability of constraint satisfaction problems (CSPs) in low-space streaming models. Inspired by this recent progress, we collate nine conjectural lower bounds against streaming algorithms for CSPs, some of which appear here for the first time.
翻译:本文综述了多位作者近期在低空间流式模型下约束满足问题(CSPs)近似性理解方面的研究进展。受这些最新进展的启发,我们整理了九个针对CSPs流式算法的猜想下界,其中部分猜想为首次在此提出。