References & Citations
Computer Science > Computational Complexity
Title: Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
(Submitted on 7 Nov 2022 (this version), latest version 26 Apr 2024 (v2))
Abstract: 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.
Submission history
From: John Lapinskas [view email][v1] Mon, 7 Nov 2022 21:29:46 GMT (193kb,D)
[v2] Fri, 26 Apr 2024 16:25:47 GMT (550kb,D)
Link back to: arXiv, form interface, contact.