Essential covers were introduced by Linial and Radhakrishnan as a model that captures two complementary properties: (1) all variables must be included and (2) no element is redundant. In their seminal paper, they proved that every essential cover of the $n$-dimensional hypercube must be of size at least $\Omega(n^{0.5})$. Later on, this notion found several applications in complexity theory. We improve the lower bound to $\Omega(n^{0.52})$, and describe two applications.


翻译:Linial 和 Radhakrishnan 将基本覆盖作为一种模型,它捕捉了两个互补属性:(1) 必须包含所有变量, (2) 任何元素都不是多余的。 在它们的重要论文中,它们证明美元-维超立方体的每一个基本覆盖必须至少大小$\Omega(n ⁇ /0.5})$。 稍后,这一概念在复杂理论中发现了一些应用。 我们把下限提高到$\Omega(n ⁇ 0.52})$, 并描述了两种应用。

0
下载
关闭预览

相关内容

专知会员服务
76+阅读 · 2021年3月16日
知识图谱推理,50页ppt,Salesforce首席科学家Richard Socher
专知会员服务
105+阅读 · 2020年6月10日
开源书:PyTorch深度学习起步
专知会员服务
50+阅读 · 2019年10月11日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
已删除
将门创投
6+阅读 · 2019年6月10日
revelation of MONet
CreateAMind
5+阅读 · 2019年6月8日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年7月20日
Arxiv
0+阅读 · 2021年7月19日
Arxiv
0+阅读 · 2021年7月17日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关主题
相关资讯
已删除
将门创投
6+阅读 · 2019年6月10日
revelation of MONet
CreateAMind
5+阅读 · 2019年6月8日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员