论文标题
几乎最佳的独立性甲骨文算法，用于超图中的边缘估计
Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
论文作者
论文摘要
我们研究了一个查询模型的计算模型，其中N-Vertex K-Hypergraph只能通过其独立性甲骨文或通过其五颜六色的独立性甲骨文访问，并且每个Oracle查询可能会根据查询的大小而产生成本。在这些模型中的每一个中，我们都会获得甲骨文算法以大致计算超图的边缘，并且我们无条件地证明，对于此问题，没有甲骨文算法可能比我们的算法要比我们的算法要小得多。
We study a query model of computation in which an n-vertex k-hypergraph can be accessed only via its independence oracle or via its colourful independence oracle, and each oracle query may incur a cost depending on the size of the query. In each of these models, we obtain oracle algorithms to approximately count the hypergraph's edges, and we unconditionally prove that no oracle algorithm for this problem can have significantly smaller worst-case oracle cost than our algorithms.
