Toward a deterministic polynomial time algorithm with optimal additive query complexity

DOI10.1016/j.tcs.2011.09.005zbMath1235.68080OpenAlexW1978657617MaRDI QIDQ764325

Nader H. Bshouty, Hanna Mazzawi

Publication date: 13 March 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.09.005

zbMATH Keywords

combinatorial searchcoin weighing problemreconstructing hidden graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Related Items (1)

Exact learning from an honest teacher that answers membership queries

Cites Work

• An information-theoretic method in combinatorial theory
• Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping
• Toward a Deterministic Polynomial Time Algorithm with Optimal Additive Query Complexity
• Reconstructing Weighted Graphs with Minimal Query Complexity
• Bounds on the performance of protocols for a multiple-access broadcast channel
• How an Erdos-Renyi-type search approach gives an explicit code construction of rate 1 for random access with multiplicity feedback
• On a Combinatorial Problem in Number Theory
• Determination of a Subset from Certain Combinatorial Properties
• On Möbius Functions and a Problem in Combinatorial Number Theory
• Determining a Set from the Cardinalities of its Intersections with Other Sets
• A Combinatory Detection Problem
• Graph-Theoretic Concepts in Computer Science
• Optimal reconstruction of graphs under the additive model
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Toward a deterministic polynomial time algorithm with optimal additive query complexity