Graph bisection problem: approaches from statistical mechanics and theoretical computer science

点击翻译按钮获取中文摘要

Statistical mechanics has developed various techniques for analyzing large scale and complicated statistical models through research on complex physical systems such as spin glasses. Recently, much attention has been paid for such methodologies as foundations of efficient approximate algorithms and powerful analytical techniques in information sciences. The main objective of this research project is to deepen the understanding of the effectiveness of such methodologies by collaboration of a physicist and a theoretical computer scientist on a concrete problem. The problem that we focused on was graph bisection problems. We particularly examined the origin of the effectiveness of the ``spectral method'', which is known as a dominant approximate solver for the bisection problem. As a practical application of the graph bisection problem, we also improved an exiting method for the extraction of polarity lexicon from word networks utilizing the knowledge of statistical mechanics.