Optimal query complexity bounds for finding graphs

DOI10.1016/j.artint.2010.02.003zbMath1206.68228OpenAlexW2048252940MaRDI QIDQ991004

Sung-Soon Choi, Jeong Han Kim

Publication date: 2 September 2010

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2010.02.003

zbMATH Keywords

Fourier coefficientpseudo-Boolean functioncombinatorial searchcombinatorial group testinggraph findingcoin weighingLittlewood-Offord theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (8)

On triangle estimation using tripartite independent set queries ⋮ Generalized framework for group testing: queries, feedbacks and adversaries ⋮ A divide-and-conquer approach for reconstruction of \(\{C_{ \geq 5}\}\)-free graphs via betweenness queries ⋮ Exact learning from an honest teacher that answers membership queries ⋮ Exact learning of multitrees and almost-trees using path queries ⋮ Unnamed Item ⋮ Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions ⋮ Network verification via routing table queries

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping
• On \(B_ 2\)-sequences of vectors
• An Estimate for Concentration Functions
• On the Increase of Dispersion of Sums of Independent Random Variables
• Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
• Reconstructing Weighted Graphs with Minimal Query Complexity
• On the Fourier spectrum of monotone functions
• Learning a Hidden Matching
• Learning Theory
• Learning a Hidden Subgraph
• On the Kolmogorov-Rogozin inequality for the concentration function
• On the concentration function of a sum of independent random variables
• A Combinatory Detection Problem
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• On a lemma of Littlewood and Offord
• Graph-Theoretic Concepts in Computer Science
• Optimal reconstruction of graphs under the additive model

This page was built for publication: Optimal query complexity bounds for finding graphs