Lower Bounds for Coin-Weighing Problems

DOI10.1145/1944857.1944858MaRDI QIDQ2947551zbMATH OpenOpenAlexFDO

Authors Eric Purdy

Publication date 24 September 2015

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1944857.1944858

zbMATH Keywords

coin-weighing problems

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The average complexity of a coin-weighing problem
• scientific article; zbMATH DE number 1775407
• scientific article; zbMATH DE number 4087011
• Coin-Weighing Problems
• Lower bounds against weakly uniform circuits
• Lower time bounds for randomized computation
• Lower bounds for covering problems
• \(\mathrm{AC}^0[p]\) lower bounds against MCSP via the coin problem
• Lower bounds for Turán's problem
• Lower bound for the approximative complexity

Cited in

(3)

• A bridge between the minimal doubly resolving set problem in (folded) hypercubes and the coin weighing problem
• Partitions of \(n\) that avoid partitions of \(f\), and an application to the tiny-pan coin weighing problem
• Coin-Weighing Problems

This page was built for publication: Lower Bounds for Coin-Weighing Problems

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