Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
复制标题
伪确定性近似计数的紧密空间下界
DOI：
10.1109/focs57990.2023.00091
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Mark Sellke
中科院分区：
文献类型：
--
作者：
O. Grossman;Meghal Gupta;Mark Sellke
我们研究了流算法中最基本的问题之一：近似流中元素的数量。著名的是，[Mor 78]给出了一个随机算法，在空间$O（\log\log N）$中实现了长度至多为N的流的常数因子近似误差。我们研究了问题的伪确定性复杂性，并证明了一个紧密的$\Omega（\log N）$下界，从而解决了[GGMW 20]的问题。
We investigate one of the most basic problems in streaming algorithms: approximating the number of elements in the stream. Famously, [Mor78] gave a randomized algorithm achieving a constant-factor approximation error for streams of length at most N in space $O(\log\log N)$. We investigate the pseudo-deterministic complexity of the problem and prove a tight $\Omega(\log N)$ lower bound, thus resolving a problem of [GGMW20].
登录
查看更多内容
伪决定论：承诺和下限
DOI：
10.1145/3519935.3520043
发表时间：
2022
期刊：
Symposium on Theory of Computing (STOC
影响因子：
--
作者：
Dixon, Peter;Pavan, A.;Woude, Jason Vander;Vinodchandran, N. V.
通讯作者：
Vinodchandran, N. V.
影响因子：
--
作者：
Braverman, V.;Krauthgamer, R.;Krishnan, A.;Sapir, S.
通讯作者：
Sapir, S.
近似计数的最佳界限
DOI：
10.1145/3517804.3526225
发表时间：
2022
期刊：
Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
影响因子：
--
作者：
Nelson, Jelani;Yu, Huacheng
通讯作者：
Yu, Huacheng
DOI：
10.1109/focs.2016.87
发表时间：
2015-09
期刊：
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
O. Grossman;Dana Moshkovitz
通讯作者：
O. Grossman;Dana Moshkovitz
DOI：
--
发表时间：
2021
期刊：
Innovations in Theoretical Computer Science
影响因子：
--
作者：
Dixon, Peter;Pavan, A.;Vinodchandran, N. V.
通讯作者：
Vinodchandran, N. V.