标题： 一个平均情况下的超图着色预言机 显示英文标题

标题： A Fast Coloring Oracle for Average Case Hypergraphs

摘要： 超图$2$-着色是经典的NP难问题。 Person 和 Schacht [SODA'09] 设计了一个确定性算法，其在均匀选择的$2$-着色的$3$-一致超图上的期望运行时间是多项式的。 Lee、Molla 和 Nagle 最近将其扩展到了所有$k\geq 3$的$k$-一致超图。 这两篇论文都高度依赖于正则性引理，因此它们的分析较为复杂，运行时间隐藏了塔型常数。 本文的第一个结果是一个新的简单且基本的确定性$2$-着色算法，它重新证明了 Person-Schacht 和 Lee-Molla-Nagle 的定理，同时避免使用正则性引理。 我们还展示了如何将我们的新算法转换为一个随机算法，其平均期望运行时间仅为$O(n)$。 我们第二个且主要的结果给出了我们认为是寻找平均$2$-可着色超图的$2$-着色的最终证据。 我们定义一个着色预言机为一种算法，该算法给定顶点$v$，在尽可能少地检查边的情况下，为$v$分配红色/蓝色，使得对预言机的任何查询序列的答案都与输入的一个合法$2$-着色一致。 令人惊讶的是，我们证明存在一个着色预言机，平均而言，可以在时间$O(1)$内回答每个顶点查询。 显示英文摘要

摘要： Hypergraph $2$-colorability is one of the classical NP-hard problems. Person and Schacht [SODA'09] designed a deterministic algorithm whose expected running time is polynomial over a uniformly chosen $2$-colorable $3$-uniform hypergraph. Lee, Molla, and Nagle recently extended this to $k$-uniform hypergraphs for all $k\geq 3$. Both papers relied heavily on the regularity lemma, hence their analysis was involved and their running time hid tower-type constants. Our first result in this paper is a new simple and elementary deterministic $2$-coloring algorithm that reproves the theorems of Person-Schacht and Lee-Molla-Nagle while avoiding the use of the regularity lemma. We also show how to turn our new algorithm into a randomized one with average expected running time of only $O(n)$. Our second and main result gives what we consider to be the ultimate evidence of just how easy it is to find a $2$-coloring of an average $2$-colorable hypergraph. We define a coloring oracle to be an algorithm which, given vertex $v$, assigns color red/blue to $v$ while inspecting as few edges as possible, so that the answers to any sequence of queries to the oracle are consistent with a single legal $2$-coloring of the input. Surprisingly, we show that there is a coloring oracle that, on average, can answer every vertex query in time $O(1)$.