计算机科学 > 计算复杂性
[提交于 2025年7月11日
]
标题： 指针追踪的通信复杂性通过固定集引理
标题： Communication complexity of pointer chasing via the fixed-set lemma
摘要： 我给出了一种非常简单且似乎新的证明，用于指针追逐问题的紧致通信下界。
收藏
文献和引用工具
与本文相关的代码，数据和媒体
alphaXiv (什么是 alphaXiv？)
CatalyzeX 代码查找器 (什么是 CatalyzeX？)
DagsHub (什么是 DagsHub？)
Gotit.pub (什么是 GotitPub？)
Hugging Face (什么是 Huggingface？)
带有代码的论文 (什么是带有代码的论文？)
ScienceCast (什么是 ScienceCast？)
演示
推荐器和搜索工具
arXivLabs：与社区合作伙伴的实验项目
arXivLabs 是一个框架，允许合作伙伴直接在我们的网站上开发和分享新的 arXiv 特性。
与 arXivLabs 合作的个人和组织都接受了我们的价值观，即开放、社区、卓越和用户数据隐私。arXiv 承诺这些价值观，并且只与遵守这些价值观的合作伙伴合作。
有一个为 arXiv 社区增加价值的项目想法吗？ 了解更多关于 arXivLabs 的信息.