Unambiguous DNFs and Alon-Saks-Seymour
Unambiguous DNFs and Alon-Saks-Seymour
复制标题
明确的 DNF 和阿隆-萨克斯-西摩
DOI：
10.1109/focs52979.2021.00020
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Robin Kothari
中科院分区：
文献类型：
--
作者：
K. Balodis;S. Ben;Mika Goos;Siddhartha Jain;Robin Kothari
我们展示了一个明确的$ k $ -dnf公式，它需要CNF宽度$ \ tilde \ omega（k^{2}）$，这是最佳的，因此我们获得了对数的差异。 –saks - 图理论中的seymour问题（1991年提出），该问题问：差距在图形的色数及其双分区数之间有多大的差距？查询和通信复杂性的分离。
We exhibit an unambiguous $k$-DNF formula that requires CNF width $\tilde\Omega(k^{2})$, which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the Alon–Saks–Seymour problem in graph theory (posed in 1991), which asks: How large a gap can there be between the chromatic number of a graph and its biclique partition number? Our result is also known to imply several other improved separations in query and communication complexity.
影响因子：
1.6
作者：
Göös, Mika;Pitassi, Toniann;Watson, Thomas
通讯作者：
Watson, Thomas
DOI：
10.1007/978-3-030-62497-2
发表时间：
2021
期刊：
MATRIX book series
影响因子：
--
作者：
Chudnovsky, Maria and
通讯作者：
Chudnovsky, Maria and
影响因子：
0.7
作者：
Göös, Mika;Jayram, T. S.;Pitassi, Toniann;Watson, Thomas
通讯作者：
Watson, Thomas