Almost optimal query algorithm for hitting set using a subset query

DOI10.1016/j.jcss.2023.02.002arXiv1807.06272MaRDI QIDQ6113278

Arijit Ghosh, Gopinath Mishra, Arijit Bishnu, Saket Saurabh, Sudeshna Kolay

Publication date: 10 July 2023

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1807.06272

zbMATH Keywords

parameterized complexityquery complexityhitting setsubset queries

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On triangle estimation using tripartite independent set queries
• The size of connected hypergraphs with prescribed covering number
• Color-coding
• Intersection Theorems for Systems of Sets
• Approximating average parameters of graphs
• On Approximation Algorithms for # P
• Color-coding
• Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
• Communication Complexity
• The Power of an Example
• Parameterized Testability
• Fine-Grained Reductions from Approximate Counting to Decision
• Querying a Matrix Through Matrix-Vector Products.
• Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
• Nearly optimal edge estimation with independent set queries
• Introduction to Property Testing
• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
• Parameterized Algorithms
• New Query Lower Bounds for Submodular Function Minimization
• Edge Estimation with Independent Set Oracles
• Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems

This page was built for publication: Almost optimal query algorithm for hitting set using a subset query