We revisit noisy twenty questions estimation and study the privacy-resolution tradeoff for adaptive query procedures. Specifically, in twenty questions estimation, there are two players: an oracle and a questioner. The questioner aims to estimate target variables by posing queries to the oracle that knows the variables and using noisy responses to form reliable estimates. Typically, there are adaptive and non-adaptive query procedures. In adaptive querying, one designs the current query using previous queries and their noisy responses while in non-adaptive querying, all queries are posed simultaneously. Generally speaking, adaptive query procedures yield better performance. However, adaptive querying leads to privacy concerns, which were first studied by Tsitsiklis, Xu and Xu (COLT 2018) and by Xu, Xu and Yang (AISTATS 2021) for the noiseless case, where the oracle always provides correct answers to queries. In this paper, we generalize the above results to the more practical noisy case, by proposing a two-stage private query procedure, analyzing its non-asymptotic and second-order asymptotic achievable performance and discussing the impact of privacy concerns. Furthermore, when specialized to the noiseless case, our private query procedure achieves better performance than above-mentioned query procedures (COLT 2018, AISTATS 2021).

Motivated by the practical application of beam tracking of multiple devices in Multiple Input Multiple Output (MIMO) communication, we study the problem of non-adaptive twenty questions estimation for locating and tracking multiple moving targets under a query-dependent noisy channel. Specifically, we derive a non-asymptotic bound and a second-order asymptotic bound on resolution for optimal query procedures and provide numerical examples to illustrate our results. In particular, we demonstrate that the bound is achieved by a state estimator that thresholds the mutual information density over possible target locations. This single threshold decoding rule has reduced the computational complexity compared to the multiple threshold scheme proposed for locating multiple stationary targets (Zhou, Bai and Hero, TIT 2022). We discuss two special cases of our setting: the case with unknown initial location and known velocity, and the case with known initial location and unknown velocity. Both cases share the same theoretical benchmark that applies to stationary multiple target search in Zhou, Bai and Hero (TIT 2022) while the known initial location case is close to the theoretical benchmark for stationary target search when the maximal speed is inversely proportional to the number of queries. We also generalize our results to account for a piecewise constant velocity model introduced in Zhou and Hero (TIT 2023), where targets change velocity periodically. Finally, we illustrate our proposed algorithm for the application of beam tracking of multiple mobile transmitters in a 5G wireless network.

Due to circuit failures, defective elements that cannot adaptively adjust the phase shifts of their impinging signals in a desired manner may exist on an intelligent reflecting surface (IRS). Traditional way to locate these defective IRS elements requires a thorough diagnosis of all the circuits belonging to a huge number of IRS elements, which is practically challenging. In this paper, we will devise novel approaches under which a transmitter sends known pilot signals and a receiver localizes all the defective IRS elements just based on its over-the-air measurements reflected from the IRS. Specifically, given any set of IRS elements, we propose an efficient method to process the received signals to determine whether this cluster contains defective elements or not with a very high accuracy probability. Based on this method, we show that the over-the-air diagnosis problem belongs to the 20 questions problem, where we can adaptively change the query set at the IRS so as to localize all the defective elements as quickly as possible. Along this line, we first propose a sorted posterior matching (sortPM) based method according to the noisy 20 questions technique, which enables accurate diagnosis even if the answers about the existence of defective elements in some sets of interest are wrong at certain question and answer (Q&A) rounds due to the noisy received signals. Next, to reduce the complexity, we propose a bisection based method according to the noiseless 20 questions technique, which totally trusts the answer at each Q&A round and keeps removing half of the remaining region based on such answers. Via numerical results, we show that our proposed methods can exploit the over-the-air measurements to localize all the defective IRS elements quickly and accurately.

Motivated by the practical application of beam tracking of multiple devices in Multiple Input Multiple Output (MIMO) communication, we study the problem of non-adaptive twenty questions estimation for locating and tracking multiple moving targets under a query-dependent noisy channel. Specifically, we derive a second-order asymptotic bound on resolution for optimal query procedures and provide numerical examples to illustrate our results. In particular, we demonstrate that a single threshold decoding rule achieves the asymptotic bound. The single threshold decoding rule has reduced the computational complexity compared to the multiple threshold method proposed for locating multiple stationary targets (Zhou, Bai and Hero, TIT 2022). Finally, we illustrate our proposed algorithm for the application of beam tracking of multiple mobile transmitters in a 5G wireless network.

We study the problem of adaptive search for multiple targets using the framework of 20 questions estimation under the query-dependent noise channel. Specifically, we propose an adaptive query strategy that combines the ideas of non-adaptive search for multiple targets using random coding by Zhou, Bai and Hero (TIT, 2022) and adaptive search for one target using variable-length coding with feedback by Zhou and Hero (ISIT, 2021). Our main contribution is the derivation of the non-asymptotic and second-order asymptotic performance of our adaptive query procedure. Furthermore, we discuss the benefit of adaptivity, analytically and numerically, by comparing our results with the non-adaptive counterparts.