论文标题
布尔值在切片上的查询复杂性
Query complexity of Boolean functions on slices
论文作者
论文摘要
我们研究布尔功能在超立方体切片上的确定性查询复杂性。 $ k^{th} $ slice $ \ binom {[n]} {k} $ of HyperCube $ \ \ {0,1 \}^n $是所有$ n $ bit字符串的集合，均带有hamming strize $ k $。我们表明，在平衡的slice $ \ binom {[n]} {n/2} $需要$ n -o（\ log \ log n）$ queries上存在一个函数。我们在平衡的切片上提供了一个明确的功能，需要基于Johnson Graphs中独立集的$ n -o（\ log n）$查询。在重量-2切片上，我们表明硬函数与Ramsey图密切相关。此外，我们描述了一种简单的方法，将超立方体上的功能转换为平衡切片上的函数，同时保留了几种复杂性度量。
We study the deterministic query complexity of Boolean functions on slices of the hypercube. The $k^{th}$ slice $\binom{[n]}{k}$ of the hypercube $\{0,1\}^n$ is the set of all $n$-bit strings with Hamming weight $k$. We show that there exists a function on the balanced slice $\binom{[n]}{n/2}$ requiring $n - O(\log \log n)$ queries. We give an explicit function on the balanced slice requiring $n - O(\log n)$ queries based on independent sets in Johnson graphs. On the weight-2 slice, we show that hard functions are closely related to Ramsey graphs. Further we describe a simple way of transforming functions on the hypercube to functions on the balanced slice while preserving several complexity measures.
