论文标题
使用多彩决策Oracle进行更快的计数和采样算法
Faster Counting and Sampling Algorithms using Colorful Decision Oracle
论文作者
论文摘要
在这项工作中，我们考虑$ d $ - {\ sc hypereDge估计}和$ d $ - {\ sc hyperede示例}问题在hypergraph $ \ mathcal {h}（u（\ nathcal {h}）中，\ nathcal {f}（f}（f}（\ nathcal {h} h}）$）$ nery conformes $ n $ frack，表示一组顶点和$ \ Mathcal {f}（\ Mathcal {H}）$表示Hyperedges的集合。 The oracle access to the hypergraph is called {\sc Colorful Independence Oracle} ({\sc CID}), which takes $d$ (non-empty) pairwise disjoint subsets of vertices $A_1,\ldots,A_d \subseteq U(\mathcal{H})$ as input, and answers whether there exists a hyperedge in $\mathcal{H}$在每个$ a_i，i \ in \ {1,2，\ ldots，d \} $中都有（恰好）一个顶点。 $ d $ - {\ sc hyperedge估计}和$ d $ - {\ sc hypereedge sample}的问题本身就是组合问题本身就是重要的。另外，dell {\ it {et al。}}〜[SODA '20]确定{\ em dekistion} vs {\ em计数}许多组合优化问题的复杂性可以抽象为$ d $ - {\ sc sc hyperedge估计}问题，该问题{\ sc scid} {\ sc cid} offerce} 该论文的主要技术贡献是算法，该算法估计$ m = \ lvert {\ Mathcal {f}（\ Mathcal {h}）} \ rvert $ at $ \ wideHat {m} $ \ frac {1} {c_ {d} \ log^{d-1} n} \; \ leq \; \ frac {\ wideHat {m}}} {m} \; \ leq \; c_ {d} \ log ^{d-1} n。 $$通过最多使用$ c_ {d} \ log ^{d+2} n $许多{\ sc cid} Queries，其中$ n $表示HyperGraph $ \ Mathcal {H} $和$ C_ {D} $中的顶点数量仅取决于$ D $}。我们的结果与dell {\ it {et al。}}〜[SODA '21]的框架相结合，意味着许多基本问题的界限提高了界限。
In this work, we consider $d$-{\sc Hyperedge Estimation} and $d$-{\sc Hyperedge Sample} problem in a hypergraph $\mathcal{H}(U(\mathcal{H}),\mathcal{F}(\mathcal{H}))$ in the query complexity framework, where $U(\mathcal{H})$ denotes the set of vertices and $\mathcal{F}(\mathcal{H})$ denotes the set of hyperedges. The oracle access to the hypergraph is called {\sc Colorful Independence Oracle} ({\sc CID}), which takes $d$ (non-empty) pairwise disjoint subsets of vertices $A_1,\ldots,A_d \subseteq U(\mathcal{H})$ as input, and answers whether there exists a hyperedge in $\mathcal{H}$ having (exactly) one vertex in each $A_i, i \in \{1,2,\ldots,d\}$. The problem of $d$-{\sc Hyperedge Estimation} and $d$-{\sc Hyperedge Sample} with {\sc CID} oracle access is important in its own right as a combinatorial problem. Also, Dell {\it{et al.}}~[SODA '20] established that {\em decision} vs {\em counting} complexities of a number of combinatorial optimization problems can be abstracted out as $d$-{\sc Hyperedge Estimation} problems with a {\sc CID} oracle access. The main technical contribution of the paper is an algorithm that estimates $m= \lvert {\mathcal{F}(\mathcal{H})}\rvert$ with $\widehat{m}$ such that { $$ \frac{1}{C_{d}\log^{d-1} n} \;\leq\; \frac{\widehat{m}}{m} \;\leq\; C_{d} \log ^{d-1} n . $$ by using at most $C_{d}\log ^{d+2} n$ many {\sc CID} queries, where $n$ denotes the number of vertices in the hypergraph $\mathcal{H}$ and $C_{d}$ is a constant that depends only on $d$}. Our result coupled with the framework of Dell {\it{et al.}}~[SODA '21] implies improved bounds for a number of fundamental problems.
