期刊
DISCRETE MATHEMATICS
卷 345, 期 11, 页码 -出版社
ELSEVIER
DOI: 10.1016/j.disc.2022.113114
关键词
Exact hyperplane covers; Communication complexity; Lower bounds
类别
We describe an explicit and simple subset of the discrete hypercube that cannot be exactly covered by a number of hyperplanes that is less than exponential. The proof exploits a connection to communication complexity and heavily relies on Razborov's lower bound for disjointness.
We describe an explicit and simple subset of the discrete hypercube which cannot be exactly covered by fewer than exponentially many hyperplanes. The proof exploits a connection to communication complexity, and relies heavily on Razborov's lower bound for disjointness.(c) 2022 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据