Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
From MaRDI portal
Cites work
- An approximation algorithm for \(\#k\)-SAT
- Approximate Counting of k -Paths: Simpler, Deterministic, and in Polynomial Space
- Approximate distance oracles for planar graphs with subpolynomial error dependency
- Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
- Edge Estimation with Independent Set Oracles
- Edge sampling and graph parameter estimation via vertex neighborhood accesses
- Efficient computation of representative families with applications in parameterized and exact algorithms
- Exact and approximate pattern counting in degenerate graphs: new algorithms, hardness results, and complexity dichotomies
- Extensor-coding
- Faster all-pairs shortest paths via circuit complexity
- Faster counting and sampling algorithms using colorful decision oracle
- Fine-Grained Reductions from Approximate Counting to Decision
- Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
- scientific article; zbMATH DE number 3349081 (Why is no real title available?)
- scientific article; zbMATH DE number 7788351 (Why is no real title available?)
- Narrow sieves for parameterized paths and packings
- Nearly optimal edge estimation with independent set queries
- Non-adaptive edge counting and sampling via bipartite independent set queries
- NP is as easy as detecting unique solutions
- Parameterized query complexity of hitting set using stability of sunflowers
- Randomised enumeration of small witnesses using a decision oracle
- Randomized Approximations of Parameterized Counting Problems
- Subcubic equivalences between path, matrix, and triangle problems
- The challenges of unbounded treewidth in parameterised subgraph counting problems
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems
- Weighted min-cut: sequential, cut-query, and streaming algorithms
This page was built for publication: Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6875148)
