Streaming and Sketching Complexity of CSPs: A survey
Streaming and Sketching Complexity of CSPs: A survey
复制标题
CSP 的流式传输和草图复杂性：一项调查
DOI：
10.48550/arxiv.2205.02744
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
M. Sudan
中科院分区：
文献类型：
--
作者：
M. Sudan
在这项调查中，我们在过去十年左右的时间里描述了在计算的流媒体和素描模型中求解约束满意度问题（CSP）的复杂性。尝试解释为什么在素描算法中有一个紧密的二分法结果TR 22-065。 Shahrasbi和Ameya Velingker - 为此，他们也遇到了许多错误，并提出了一些建议。这项调查更加可读性。
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. 2012 ACM Subject Classification Theory of computation → Sketching and sampling TR 22-065. Acknowledgements I want to thank Santhoshini Velusamy for introducing me to this wonderful line of research. I want to thank her and all other co-authors – Chi-Ning Chou, Sasha Golovnev, Noah Singer, Raghuvansh Saxena, Amirbehshad Shahrasbi and Ameya Velingker – for the collaborations and discussions which informed this survey. They also caught numerous errors and gave suggestions that have hopefully made this survey more readable. I want to thank the organizers of ICALP 2022 for inviting me to write this survey, and to David Woodruff in particular for the additional encouragement and nudges that were crucial to get me going.
登录
查看更多内容
概述（弱）君主制谓词的近似性
DOI：
--
发表时间：
2022
期刊：
{APPROX/RANDOM} 2022
影响因子：
--
作者：
Chou, Chi-Ning;Golovnev, Alexander;Shahrasbi, Amirbehshad;Sudan, Madhu;Velusamy, Santhoshini
通讯作者：
Velusamy, Santhoshini
用于近似 CSP 的线性空间流下界
DOI：
10.1145/3519935.3519983
发表时间：
2022
期刊：
{STOC} '22: 54th Annual {ACM} {SIGACT} Symposium on Theory of Computing
影响因子：
--
作者：
Chou, Chi-Ning;Golovnev, Alexander;Sudan, Madhu;Velingker, Ameya;Velusamy, Santhoshini
通讯作者：
Velusamy, Santhoshini
循环计数、MAX-CUT、匹配大小和其他问题的多通道图流下限
DOI：
--
发表时间：
2020
期刊：
Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Assadi, Sepehr;Kol, Gillat;Saxena, Raghuvansh;Yu, Huacheng
通讯作者：
Yu, Huacheng
通过流式 XOR 引理进行参数估计和属性测试的图流式下界
DOI：
10.1145/3406325.3451110
发表时间：
2021
期刊：
2021
影响因子：
--
作者：
Assadi, Sepehr;N, Vishvajeet
通讯作者：
N, Vishvajeet