RBP algorithm for lossy compression in reduced, ultrasparse GF(q) codes

gf-rbp.tgz24.36 KB

This code implements a novel data compression technique for binary symmetric sources based on the cavity method over GF(q), the Galois Field of order q. We present a scheme of low complexity and near-optimal empirical performance. The compression step is based on a reduction of a sparse low-density parity-check code over GF(q) and is done through the so-called reinforced belief-propagation equations. These reduced codes appear to have a nontrivial geometrical modification of the space of codewords, which makes such compression computationally feasible.

Computer Go

Go is an ancient Chinese game that originated some 4000 years ago and has still great popularity nowadays. Computer Go on the other hand has made little progress in these 4000 years: best go programs are rated like middle-to-weak amateur human players. We will discuss one recent approach to computer go [¹], based on a mixture of two relatively well known strategies: the UCT algorithm and Monte Carlo, which happens to be the most successful one to date.

[1] Modification of UCT with Patterns in Monte-Carlo Go, S. Gerlly, Y. Wang, R. Munos and O.Teytaud, INRIA Technical Report, 2006.

Wed, 04/02/2009 - 12:30
Alfredo Braunstein
Syndicate content