Random clique codes

Abstract—A new family of associative memories based on sparse neural networks has been recently introduced. These memories achieve excellent performance thanks to the use of error-correcting coding principles. In this work, we introduce a new family of codes termed clique codes. These codes are based on the cliques in balanced n-partite graphs describing associative memories. In particular, we study an ensemble of random clique codes, and prove that such ensemble contains asymptotically good codes. Furthermore, these codes can be efficiently decoded using the neural networks based associative memories with limited complexity and memory consumption. I