Hard combinatorial optimisation problems deal with the
search for the ground state of discrete systems under
strong frustration such as spin glasses. A
transformation of state variables may enhance
computational tractability. It has been argued that
these state encodings are to be chosen invertible to
retain the original size of the state space. Here we
show how redundant non-invertible encodings enhance
optimisation by enriching the density of low-energy
states. In addition, smooth landscapes may be
established on encoded state spaces to guide local
search dynamics towards the ground state
[e-print arXiv:1104.5024].
Coffee and cookies will be served 15 minutes before the start of the seminar
Contact details:
Manuel Matías Contact form