
In this paper, we design efficient algorithms to approximately count the number of edges of a given $k$-hypergraph, and to sample an approximately uniform random edge. The hypergraph is not given explicitly, and can be accessed only through its colourful independence oracle: The colourful independence oracle returns yes or no depending on whether a given subset of the vertices contains an edge that is colourful with respect to a given vertex-colouring. Our results extend and/or strengthen recent results in the graph oracle literature due to Beame et al. (ITCS 2018), Dell and Lapinskas (STOC 2018), and Bhattacharya et al. (ISAAC 2019). Our results have consequences for approximate counting/sampling: We can turn certain kinds of decision algorithms into approximate counting/sampling algorithms without causing much overhead in the running time. We apply this approximate-counting/sampling-to-decision reduction to key problems in fine-grained complexity (such as $k$-SUM, $k$-OV and weighted $k$-Clique) and parameterised complexity (such as induced subgraphs of size $k$ or weight-$k$ solutions to CSPs).
oracle access, FOS: Computer and information sciences, name=Algorithms and Complexity, Parameterized complexity, tractability and kernelization, Computational Complexity (cs.CC), Hypergraphs, colourful independence oracle, fine-grained complexity, graph oracles, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), FPTRAS, approximate counting, parameterized complexity, k-hypergraphs, Randomized algorithms, uniform edge sampling, /dk/atira/pure/core/keywords/algorithms_and_complexity, Approximation algorithms, 004, Computer Science - Computational Complexity, sampling algorithms, Graph theory (including graph drawing) in computer science, k-hypergraph
oracle access, FOS: Computer and information sciences, name=Algorithms and Complexity, Parameterized complexity, tractability and kernelization, Computational Complexity (cs.CC), Hypergraphs, colourful independence oracle, fine-grained complexity, graph oracles, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), FPTRAS, approximate counting, parameterized complexity, k-hypergraphs, Randomized algorithms, uniform edge sampling, /dk/atira/pure/core/keywords/algorithms_and_complexity, Approximation algorithms, 004, Computer Science - Computational Complexity, sampling algorithms, Graph theory (including graph drawing) in computer science, k-hypergraph
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 12 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
