Lune

FOCS2023顶会

Slicing all Edges of an n-cube Requires n2/3 Hyperplanes

Ohad Klein

2023年份
1被引次数

摘要

Consider the n-cube graph with vertices {−1,1}n\{-1,1\}^{n} and edges connecting vertices with Hamming distance 1. How many hyperplanes in Rn\mathbb{R}^{n} are needed in order to dissect all edges? We show that at least Ω~(n2/3)\widetilde{\Omega}(n^{2/3}) are needed, which improves the previous bound of Ω(n0.51)\Omega(n^{0.51}) by Yehuda and Yehudayoff.

问问这篇 Paper

智能体会读完全文。

Lune 把这篇 Paper 索引到了每一个公式,引用它的顶会 Paper 也一样。你提问,回答直接引用原文。

可以从这些问题问起

智能体调用

Luneget_paper_fulltext

在 Lune 里问

免费开始,无需绑卡

相关 Paper

黄昏的海面,两侧是细线勾勒的悬崖