Preprint
Aug 2026
Interaction Is Not Necessary for Order-Optimal 1-Bit Mean Estimation
A randomized fully non-adaptive protocol is constructed that fixes all queries before observing the data and matches the optimal adaptive sample complexity, giving a negative answer to the COLT 2026 open problem asking whether interaction is necessary for order-optimal one-bit mean estimation.
Jiachen Hu, Han Zhong
· 0 citations