Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle

DOI10.1137/19M130604XzbMath1502.68220OpenAlexW4283816481MaRDI QIDQ5092506

John Lapinskas, Kitty Meeks, Holger Dell

Publication date: 22 July 2022

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/19m130604x

zbMATH Keywords

parameterized complexityapproximate countingFPTRASfine-grained complexitygraph oracles

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Randomized algorithms (68W20) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (2)

Parameterised counting in logspace ⋮ Almost optimal query algorithm for hitting set using a subset query

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Constrained multilinear detection and generalized graph motifs
• On a class of \(O(n^2)\) problems in computational geometry
• Constrained multilinear detection for faster functional motif discovery
• The complexity of computing the permanent
• On triangle estimation using tripartite independent set queries
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• An approximation trichotomy for Boolean \#CSP
• Random generation of combinatorial structures from a uniform distribution
• NP is as easy as detecting unique solutions
• Counting \(H-\)colorings of partial \(k-\)trees
• The hardness of embedding grids and walls
• Randomised enumeration of small witnesses using a decision oracle
• The relative complexity of approximate counting problems
• Finding and counting vertex-colored subtrees
• The parameterised complexity of counting connected subgraphs and graph motifs
• Parametrized complexity theory.
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Randomized Approximations of Parameterized Counting Problems
• Color-coding
• Faster All-Pairs Shortest Paths via Circuit Complexity
• Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
• Completeness for First-order Properties on Sparse Structures with Algorithmic Applications
• Faster decision of first-order graph properties
• A Complexity Trichotomy for Approximately Counting List H -Colorings
• Counting Answers to Existential Questions
• More consequences of falsifying SETH and the orthogonal vectors conjecture
• Fine-grained reductions from approximate counting to decision
• Counting hypergraph colourings in the local lemma regime
• Zeros of Holant problems: locations and algorithms
• Near-optimal Linear Decision Trees for k-SUM and Related Problems
• Exact Weight Subgraphs and the k-Sum Conjecture
• More Applications of the Polynomial Method to Algorithm Design
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs

This page was built for publication: Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle