Lower Bound of Coin Counting Problem

Abstract

We have n coins of two weights. We also have a balance scale to measure the weights of the coins. The objective is to find the number of heavy coins with as few measurement as possible. This problem is known as "coin-counting problem". A sub-problem of this problem is, optimally find if the number of the heavy coins is even or odd. This problem is known as "coin-parity problem". It was first proposed by "Laszlo Babai"of "University of Chicago". There is a known adaptive algorithm which solves the coin-counting problem in O(log2n) time. By modifying that algorithm we can also solve the parity problem in O(logn) time. The oblivious lower bound of coin-counting problem is O( p n). This result was proved by "Eric Purdy" on the paper "Lower Bound of coin-counting problem" (1). In the first section of this thesis we have discussed about oblivious lower bound of the counting problem and showed a tight adaptive (logn) bound on coin parity problem. All these result are based on the eric purdy’s "Lower Bound of coin-counting problems" paper. There is a trivial adaptive lower bound of the coin-counting problem which is logn. As we can see adaptive coin-counting problem does not have a tight bound. The objective of this thesis is to give an improvement on the lower bound of adaptive coin counting problem. In chapter 4 we have given a proof of the adaptive lower bound of coin-counting problem is log2n + loglogn. We interpreted each one of the coin configuration into a boolean-vector. The main idea is to check which of these Boolean-vectors can go to the same leaf of the decision tree . This creates a partition of Boolean-vectors. By counting the partitions give us the total number of leaf nodes in the decision tree. Now taking log of this number gives us the height of the decision tree and that’s our required lower bound.