On the Worst-Case Complexity of Gibbs Decoding for Reed--Muller Codes

Xuzhe Xia, Nicholas Kwan, Lele Wang

Reed--Muller (RM) codes are known to achieve capacity on binary symmetric channels (BSC) under the Maximum a Posteriori (MAP) decoder. However, it remains an open problem to design…