Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma
Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma
复制标题
通过流式 XOR 引理进行参数估计和属性测试的图流式下界
DOI：
10.1145/3406325.3451110
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
N, Vishvajeet
中科院分区：
文献类型：
--
作者：
Assadi, Sepehr;N, Vishvajeet
我们研究了图流算法的参数估计和属性测试问题，如估计最大匹配和最大切割的大小，最小生成树的重量，或测试，如果一个图是连接的或无环与远离这些属性。我们开发了一个新的下界技术，证明了对于许多感兴趣的问题，包括所有上述问题，获得（1+）-近似需要eitrile Ω（1）空间或Ω（1/）通行证，即使是在高度限制的图族，如有界度平面图。对于这些问题中的多个，这个界限与现有算法相匹配，因此是（渐近）最优的。我们的结果大大加强了先验下界，即使是任意图：从[Verbin，Yu; SODA 2011]的有影响力的工作开始，这些问题的单遍算法有过多的下界;然而，最近在[Assadi，Kol，Saxena，Yu; FOCS 2020]排除了这些问题的指数较小（log（1/log））通道的子线性空间算法。我们证明的一个关键成分是一个简单的扩展XOR引理，一个通用的硬度放大结果，我们证明：非正式地说，如果ap-passs-space流算法只能解决一个决策问题的优势δ > 0比随机猜测，那么它不能解决异或的独立副本的问题的优势比δ> 0。这个结果可以是独立的兴趣和有用的其他流的下限以及。
We studyspace-pass tradeoffsin graph streaming algorithms for parameter estimation and property testing problems such as estimating the size of maximum matchings and maximum cuts, weight of minimum spanning trees, or testing if a graph is connected or cycle-free versus being far from these properties. We develop a new lower bound technique that proves that for many problems of interest, including all the above, obtaining a (1+є)-approximation requires eithernΩ(1)space or Ω(1/є) passes, even on highly restricted families of graphs such as bounded-degree planar graphs. For multiple of these problems, this bound matches those of existing algorithms and is thus (asymptotically) optimal. Our results considerably strengthen prior lower bounds even for arbitrary graphs: starting from the influential work of [Verbin, Yu; SODA 2011], there has been a plethora of lower bounds for single-pass algorithms for these problems; however, the only multi-pass lower bounds proven very recently in [Assadi, Kol, Saxena, Yu; FOCS 2020] rules out sublinear-space algorithms with exponentially smallero(log(1/є)) passes for these problems. One key ingredient of our proofs is a simplestreaming XOR Lemma, a generic hardness amplification result, that we prove: informally speaking, if ap-passs-space streaming algorithm can only solve a decision problem with advantage δ > 0 over random guessing, then it cannot solve XOR of ℓ independent copies of the problem with advantage much better than δℓ. This result can be of independent interest and useful for other streaming lower bounds as well.
登录
查看更多内容
动态数据流中加权匹配的次线性估计
DOI：
10.1007/978-3-662-48350-3_23
发表时间：
2015
期刊：
ArXiv
影响因子：
--
作者：
Marc Bury;Chris Schwiegelshohn
通讯作者：
Chris Schwiegelshohn
DOI：
10.1145/2789149.2789161
发表时间：
2015
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Omri Weinstein
通讯作者：
Omri Weinstein
o(n) 空间中的动态图流算法
影响因子：
1.1
作者：
Zengfeng Huang;Pan Peng
通讯作者：
Pan Peng
再看一下图形流中的三角形计数
DOI：
10.1016/j.tcs.2014.07.025
发表时间：
2014
期刊：
ArXiv
影响因子：
--
作者：
Graham Cormode;H. Jowhari
通讯作者：
H. Jowhari
DOI：
10.1145/1374376.1374470
发表时间：
2008
期刊：
Proceedings of the fortieth annual ACM symposium on Theory of computing
影响因子：
--
作者：
Amit Chakrabarti;Graham Cormode;A. Mcgregor
通讯作者：
A. Mcgregor