*Marc Mézard and Andrea Montanari*

- Published in print:
- 2009
- Published Online:
- September 2009
- ISBN:
- 9780198570837
- eISBN:
- 9780191718755
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198570837.003.0006
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics

This chapter studies the simplest error correcting code ensemble, introduced by Shannon, in which codewords are independent random points on the hypercube. This code achieves optimal error correcting ...
More

This chapter studies the simplest error correcting code ensemble, introduced by Shannon, in which codewords are independent random points on the hypercube. This code achieves optimal error correcting performances, and offers a constructive proof of the ‘direct’ part of the channel coding theorem: it is possible to communicate with vanishing error probability as long as the communication rate is smaller than the channel capacity. It is also very closely related to the Random Energy Model.Less

This chapter studies the simplest error correcting code ensemble, introduced by Shannon, in which codewords are independent random points on the hypercube. This code achieves optimal error correcting performances, and offers a constructive proof of the ‘direct’ part of the channel coding theorem: it is possible to communicate with vanishing error probability as long as the communication rate is smaller than the channel capacity. It is also very closely related to the Random Energy Model.

*Marc Mézard and Andrea Montanari*

- Published in print:
- 2009
- Published Online:
- September 2009
- ISBN:
- 9780198570837
- eISBN:
- 9780191718755
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198570837.003.0007
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics

Number partitioning is one of the most basic optimization problems. It is very easy to state: ‘Given the values of N assets, is there a fair partition of them into two sets?’ Nevertheless, it is very ...
More

Number partitioning is one of the most basic optimization problems. It is very easy to state: ‘Given the values of N assets, is there a fair partition of them into two sets?’ Nevertheless, it is very difficult to solve: it belongs to the NP-complete category, and the known heuristics are often not very good. It is also a problem with practical applications, for instance in multiprocessor scheduling. This chapter focuses on a particularly difficult case: the partitioning of a list of independent uniformly distributed random numbers. It discusses the phase transition occurring when the range of numbers varies, and shows that low cost configurations — the ones with a small unbalance between the two sets — can be seen as independent energy levels. Hence the model behaves analogously to the Random Energy Model.Less

Number partitioning is one of the most basic optimization problems. It is very easy to state: ‘Given the values of *N* assets, is there a fair partition of them into two sets?’ Nevertheless, it is very difficult to solve: it belongs to the NP-complete category, and the known heuristics are often not very good. It is also a problem with practical applications, for instance in multiprocessor scheduling. This chapter focuses on a particularly difficult case: the partitioning of a list of independent uniformly distributed random numbers. It discusses the phase transition occurring when the range of numbers varies, and shows that low cost configurations — the ones with a small unbalance between the two sets — can be seen as independent energy levels. Hence the model behaves analogously to the Random Energy Model.