Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams
Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams
复制标题
通用关系、采样器和在流中查找重复项的最佳下界
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Mobin Yahyazadeh
中科院分区：
文献类型：
--
作者：
M. Kapralov;Jelani Nelson;J. Pachocki;Zhengyu Wang;David P. Woodruff;Mobin Yahyazadeh
在通信问题UR(Universal Relationship)中，Alice和Bob分别收到x，y∊；{0，1\}^n，承诺x≠；y。最后一个收到消息的玩家必须输出一个索引i，使得x_i≠；y_i。我们证明了这个问题在公共硬币模型中的随机单向通信复杂性正好是失败概率δ；)的\theta(\minn，\log(1/δ；))\log^2(\frac n{\log(1/δ；)})。即使承诺了\mathop{Support}(Y)⊄；\mathop{Support}(X)，我们的下限仍然成立。作为推论，对于0≤；p的0-p流，我们得到了严格旋转门流中ℓ；_p-抽样的最优下界
In the communication problem UR (universal relation), Alice and Bob respectively receive x, y ∊{0,1\}^n with the promise that x≠ y. The last player to receive a message must output an index i such that x_i≠ y_i. We prove that the randomized one-way communication complexity of this problem in the public coin model is exactly \Theta(\min\{n,\log(1/δ)\log^2(\frac n{\log(1/δ)})\}) for failure probability δ. Our lower bound holds even if promised \mathop{support}(y)⊄ \mathop{support}(x). As a corollary, we obtain optimal lower bounds for ℓ_p-sampling in strict turnstile streams for 0\le p streams for 0 ≤ p
参数化流：最大匹配和顶点覆盖
DOI：
10.1137/1.9781611973730.82
发表时间：
2015
期刊：
影响因子：
--
作者：
Rajesh Hemant Chitnis;Graham Cormode;Mohammad Taghi Hajiaghayi;Morteza Monemizadeh
通讯作者：
Morteza Monemizadeh
DOI：
10.1137/1.9781611974331.ch92
发表时间：
2016-01
期刊：
--
影响因子：
--
作者：
R. Chitnis;Graham Cormode;Hossein Esfandiari;M. Hajiaghayi;A. Mcgregor;M. Monemizadeh;Sofya Vorotnikova
通讯作者：
R. Chitnis;Graham Cormode;Hossein Esfandiari;M. Hajiaghayi;A. Mcgregor;M. Monemizadeh;Sofya Vorotnikova