Tight bounds and conjectures for the isolation lemma
Tight bounds and conjectures for the isolation lemma
复制标题
隔离引理的紧界和猜想
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
David G. Harris
中科院分区：
文献类型：
--
作者：
V. Faber;David G. Harris
给定超图$ h $和权重函数$ W：v
ightarrow {1，点，m} $在其顶点上，我们说$ w $是隔离的，如果完全存在最小重量的一个边缘$ w（e）= sum_ {i in e} w（i）$。分离引理是Mulmuley等人引入的组合原理。 Al（1987）对隔离权重函数的数量进行了下限。 Mulmuley将其用作寻找完美图形匹配的并行算法的基础。它具有许多其他应用程序，用于并行算法，并将一般搜索问题减少到唯一的搜索问题（其中有一个或零解决方案）。
Mulmuley等人给出的原始结合。最近被Ta-Shma（2015）改进。在本文中，我们在隔离权重功能的数量上显示了改进的下限，并且猜想极端情况是$ h $由$ n $ singleton边缘组成时。当$ m gg n $时，我们的改进的界限会渐近地匹配这个极端案例。
我们能够证明此猜想在许多特殊情况下都存在：当$ h $是线性超图或1级化时，或者当$ m = 2 $时。我们还表明，当$ m gg n gg 1 $时，它渐近。
Given a hypergraph $H$ and a weight function $w: V
ightarrow {1, dots, M}$ on its vertices, we say that $w$ is isolating if there is exactly one edge of minimum weight $w(e) = sum_{i in e} w(i)$. The Isolation Lemma is a combinatorial principle introduced in Mulmuley et. al (1987) which gives a lower bound on the number of isolating weight functions. Mulmuley used this as the basis of a parallel algorithm for finding perfect graph matchings. It has a number of other applications to parallel algorithms and to reductions of general search problems to unique search problems (in which there are one or zero solutions).
The original bound given by Mulmuley et al. was recently improved by Ta-Shma (2015). In this paper, we show improved lower bounds on the number of isolating weight functions, and we conjecture that the extremal case is when $H$ consists of $n$ singleton edges. When $M gg n$ our improved bound matches this extremal case asymptotically.
We are able to show that this conjecture holds in a number of special cases: when $H$ is a linear hypergraph or is 1-degenerate, or when $M = 2$. We also show that it holds asymptotically when $M gg n gg 1$.
准NC中的二分完美匹配
DOI：
10.1145/2897518.2897564
发表时间：
2016
期刊：
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing
影响因子：
--
作者：
Stephen A. Fenner;Rohit Gurjar;Thomas Thierauf
通讯作者：
Thomas Thierauf