Toward a deterministic polynomial time algorithm with optimal additive query complexity

DOI10.1016/J.TCS.2011.09.005MaRDI QIDQ764325zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Toward a deterministic polynomial time algorithm with optimal additive query complexity
• On the coin weighing problem with the presence of noise
• Optimally reconstructing weighted graphs using queries
• scientific article; zbMATH DE number 1222833
• Optimal query complexity bounds for finding graphs

Cites work

• scientific article; zbMATH DE number 41347 (Why is no real title available?)
• scientific article; zbMATH DE number 3499765 (Why is no real title available?)
• scientific article; zbMATH DE number 3532378 (Why is no real title available?)
• scientific article; zbMATH DE number 1222833 (Why is no real title available?)
• scientific article; zbMATH DE number 5485589 (Why is no real title available?)
• scientific article; zbMATH DE number 3248639 (Why is no real title available?)
• A Combinatory Detection Problem
• An information-theoretic method in combinatorial theory
• Bounds on the performance of protocols for a multiple-access broadcast channel
• Determination of a Subset from Certain Combinatorial Properties
• Determining a Set from the Cardinalities of its Intersections with Other Sets
• Graph-Theoretic Concepts in Computer Science
• How an Erdos-Renyi-type search approach gives an explicit code construction of rate 1 for random access with multiplicity feedback
• On Möbius Functions and a Problem in Combinatorial Number Theory
• On a Combinatorial Problem in Number Theory
• Optimal reconstruction of graphs under the additive model
• Optimally reconstructing weighted graphs using queries
• Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping
• Reconstructing weighted graphs with minimal query complexity
• Toward a deterministic polynomial time algorithm with optimal additive query complexity

Cited in

(9)

• Optimal query complexity bounds for finding graphs
• Toward a deterministic polynomial time algorithm with optimal additive query complexity
• On the coin weighing problem with the presence of noise
• Exact learning from an honest teacher that answers membership queries
• Reconstructing weighted graphs with minimal query complexity
• Reconstructing weighted graphs with minimal query complexity
• Simple PCPs with poly-log rate and query complexity
• Addendum to ``Choiceless polynomial time
• On parity check \((0, 1)\)-matrix over \(\mathbb{Z}_p\)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q764325)