All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD4-S7-T2.2
Paper Title Efficient Bee Identification
Authors Han Mao Kiah, Nanyang Technological University, Singapore; Alexander Vardy, Hanwen Yao, University of California San Diego, United States
Session D4-S7-T2: Information Theory for Biology
Chaired Session: Friday, 16 July, 00:00 - 00:20
Engagement Session: Friday, 16 July, 00:20 - 00:40
Abstract The bee-identification problem, formally defined by Tandon, Tan and Varshney (2019), requires the receiver to identify "bees'' using a set of unordered noisy measurements. In this previous work, Tandon, Tan and Varshney studied error exponents and showed that decoding the measurements {\em jointly} results in a significantly smaller error exponent. Here, we study efficient ways of performing joint decoding. First, by reducing to the problem of finding perfect matching and minimum-cost matchings, we obtain joint decoders that run in time quadratic and cubic in the number of "bees" for the binary erasure (BEC) and binary symmetric channels (BSC), respectively. Next, by studying the matching algorithms in the context of channel coding, we further reduce the running times by using classical tools like peeling decoders and list-decoders. In particular, we show that our identifier algorithms when used with Reed-Muller codes terminates in almost linear and quadratic time for BEC and BSC, respectively.