Analysis of a Randomized Local Search Algorithm for LDPCC Decoding Problem

摘要

We propose an approach for analyzing the average performance of a given (randomized) local search algorithm for a constraint satisfaction problem. Our approach consists of two approximations. Using a randomized algorithm for LDPCC decoding, we experimentally investigate the reliability of these approximations and show that they could be used as a tool for analyzing the average performance of randomized local search algorithms.