Oblivious algorithms for the Max-kAND Problem
Oblivious algorithms for the Max-kAND Problem
复制标题
Max-kAND 问题的遗忘算法
DOI：
10.48550/arxiv.2305.04438
复制
发表时间：
2023
影响因子：
2.9
通讯作者：
Noah G. Singer
中科院分区：
文献类型：
--
作者：
Noah G. Singer
在最近关于限制满意度问题的流算算法（CSP）方面的著作中，我们定义和分析了最大$ K $和问题的遗忘算法。这概括了Feige和Jozeph（算法'15）对Max-Dicut的遗忘算法的定义，这是一种最大$ 2 $ and的特殊情况。仅根据称为变量的偏差的数量，忽略的算法将每个变量围绕每个变量。对于每种遗忘算法，我们设计了一个所谓的“避免因子的线性程序”（LP），该程序捕获了其最差的实例，将Feige和Jozeph的一个概括为Max-Dicut。然后，偏离他们的工作，我们对这些（无限多！）LPS进行了完全明确的分析。特别是，我们表明，对于所有$ k $，最大$ k $的遗忘算法，并且证明我们称之为“超稳定”算法的特殊算法子类。我们的结果对流算法有影响：概括萨克斯纳，歌手，苏丹和velusamy的Max-Dicut（SODA'23）的结果，我们证明，无限多CSP的流模型之间存在某些分离结果：对于每个$ K $ ，$ o（\ log n）$ - 最大$ k $的空间素描算法，并在$ o（\ sqrt）中是最佳的n）$ - 可以在（a）$ o（\ log n）$ - 在随机订购假设下的空间中击败空间，（b）$ o（n^{1-1/k} d^{1/ k}）$空间在最大值 - $ d $假设下。即使在先前已知的Max-Dicut案例中，我们的分析证明也为这些分离结果提供了更全面的，无计算机的图片。
Motivated by recent works on streaming algorithms for constraint satisfaction problems (CSPs), we define and analyze oblivious algorithms for the Max-$k$AND problem. This generalizes the definition by Feige and Jozeph (Algorithmica '15) of oblivious algorithms for Max-DICUT, a special case of Max-$2$AND. Oblivious algorithms round each variable with probability depending only on a quantity called the variable's bias. For each oblivious algorithm, we design a so-called"factor-revealing linear program"(LP) which captures its worst-case instance, generalizing one of Feige and Jozeph for Max-DICUT. Then, departing from their work, we perform a fully explicit analysis of these (infinitely many!) LPs. In particular, we show that for all $k$, oblivious algorithms for Max-$k$AND provably outperform a special subclass of algorithms we call"superoblivious"algorithms. Our result has implications for streaming algorithms: Generalizing the result for Max-DICUT of Saxena, Singer, Sudan, and Velusamy (SODA'23), we prove that certain separation results hold between streaming models for infinitely many CSPs: for every $k$, $O(\log n)$-space sketching algorithms for Max-$k$AND known to be optimal in $o(\sqrt n)$-space can be beaten in (a) $O(\log n)$-space under a random-ordering assumption, and (b) $O(n^{1-1/k} D^{1/k})$ space under a maximum-degree-$D$ assumption. Even in the previously-known case of Max-DICUT, our analytic proof gives a fuller, computer-free picture of these separation results.
登录
查看更多内容
改进的流算法通过平滑快照实现最大定向剪切
DOI：
10.1109/focs57990.2023.00055
发表时间：
2023
期刊：
64th {IEEE} Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Saxena, Raghuvansh R.;Singer, Noah G.;Sudan, Madhu;Velusamy, Santhoshini
通讯作者：
Velusamy, Santhoshini
概述（弱）君主制谓词的近似性
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
具有随机排序约束的 CSP 的流复杂性
DOI：
--
发表时间：
2023
期刊：
{SODA} 2023
影响因子：
--
作者：
Saxena, Raghuvansh R.;Singer, Noah;Sudan, Madhu;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