论文标题
蜜蜂识别问题的有效算法
Efficient Algorithms for the Bee-Identification Problem
论文作者
论文摘要
由Tandon，Tan和Varshney（2019）正式定义的蜜蜂识别问题要求接收器使用一组无序的嘈杂测量值识别“蜜蜂”。在此前的工作中，Tandon，Tan和Varshney研究了误差指数，并表明解码测量值共同导致误差指数明显较小。 在这项工作中，我们研究了与该联合解码器相关的算法。首先，我们演示了如何有效执行关节解码。通过减少找到完美匹配和最低成本匹配的问题，我们获得了分别在二进制擦除（BEC）和二进制对称通道（BSC）的“蜜蜂”数量中以二次二次和立方运行的关节解码器。接下来，通过在频道编码的上下文中研究匹配算法，我们通过使用剥离解码器和列表编码器（例如剥离解码器），进一步减少运行时间。特别是，我们表明，当与芦苇毛刺代码一起使用时，我们的标识符算法分别以BEC和BSC的几乎线性和二次时间终止。 最后，对于明确的代码手册，我们研究了这些联合解码器无法正确识别“蜜蜂”。具体而言，我们提供了估计给定代码簿错误识别概率的实用方法。
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 jointly results in a significantly smaller error exponent. In this work, we study algorithms related to this joint decoder. First, we demonstrate how to perform joint decoding efficiently. 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 terminate in almost linear and quadratic time for BEC and BSC, respectively. Finally, for explicit codebooks, we study when these joint decoders fail to identify the "bees" correctly. Specifically, we provide practical methods of estimating the probability of erroneous identification for given codebooks.
