EUVIMEDEUVIMED entdecken
Crossref

Lower Bounds for Coin-Weighing Problems

Eric Purdy

ACM Transactions on Computation Theory · 2011

DOI: 10.1145/1944857.1944858 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Computation Theory, 2011. Verfasst von Eric Purdy. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 11 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Among a set of n coins of two weights (good and bad), and using a balance, we wish to determine the number of bad coins using as few measurements as possible. There is a known adaptive decision tree that answers this question in O ((log( n )) 2 ) measurements, and a slight modification of this decision tree determines the parity of the number of bad coins in O (log n ). In this article, we prove an Ω(\sqrt{ n }) lower bound on the depth of any oblivious decision tree which solves either the counting or the parity problem. Our lower bound can also be applied to any function of high average sensitivity, which includes most random functions and most random symmetric functions. With a slight generalization of this result, we derive lower bounds for the size of threshold circuits for a wide class of Boolean functions. We demonstrate an exponential gap between the nonadaptive and adaptive coin-weighing complexities of the counting and parity problems. We prove a tight Θ (log n ) bound on the adaptive coin-weighing complexity of the parity problem.

Zitieren

APA

Purdy, E. (2011). Lower Bounds for Coin-Weighing Problems. ACM Transactions on Computation Theory. https://doi.org/10.1145/1944857.1944858

Vancouver

Purdy E. Lower Bounds for Coin-Weighing Problems. ACM Transactions on Computation Theory. 2011. doi:10.1145/1944857.1944858

BibTeX
@article{Purdy2011,
  author = {Purdy, Eric},
  title = {Lower Bounds for Coin-Weighing Problems},
  journal = {ACM Transactions on Computation Theory},
  year = {2011},
  doi = {10.1145/1944857.1944858}
}
Kostenlos starten →