Finding N bits using O(N/Log(N)) sums

Abstract

The problem we are trying to solve sounds as follows: You are given $N$ bits. Find the value of each bit. We will show a technique which enables finding the values of $N$ bits using $O(\frac{N}{\log N})$ subsequence-sum queries. The algorithm consists of two phases: Constructing the queries for each layer and using the queries for a particular layer to get the value of every bit. We described the following technique in this blog [1], which was inspired by this article [2]. It should be noted that this number of queries is indeed the optimal one for finding all $N$ bits of a binary array, since each subsequence-sum queries offers us at most $\log_{2} N$ bits of information.