|
|
Hierarchical solution and the structure of order parameters in the mean-field theory of spin glasses and related materials
Klíč, Antonín ; Janiš, Václav (vedoucí práce) ; Zahradník, Miloš (oponent) ; Zdeborová, Lenka (oponent)
V práci analyzujeme, jak dochází k narušení replikové symetrie v Sherrington- Kirkpatrickově (SK) modelu a v p stavovém Pottsově skle pro p ≤ 4. Představíme obecnou metodu pro odvození asymptotického řešení pro libovolný počet hier- archií narušení replikové symetrie. Pro oba modely hledáme řešení v blízkosti kritického bodu v nulovém vnějším poli a pro SK model též v nenulovém vnějším poli v blízkosti Almeida-Thoulessově linii nestability. Ukážeme, že pro SK model jsou všechna řešení s konečným počtem hierarchií nestabilní a že pouze řešení s nekonečně mnoha hierarchiemi je marginálně stabilní ve skelné fázi. U Pottsova skla najdeme navíc jednokrokové lokálně stabilní řešení koexistující s marginálně stabilním řešením s nekonečně mnoha hierarchiemi pro p > p∗ ≈ 2.82. Ukáže se, že lokálně stabilní řešení má menší volnou energii než druhé marginálně stabilní řešení. 1
|
|
|
Hierarchical solution and the structure of order parameters in the mean-field theory of spin glasses and related materials
Klíč, Antonín ; Janiš, Václav (vedoucí práce) ; Zahradník, Miloš (oponent) ; Zdeborová, Lenka (oponent)
V práci analyzujeme, jak dochází k narušení replikové symetrie v Sherrington- Kirkpatrickově (SK) modelu a v p stavovém Pottsově skle pro p ≤ 4. Představíme obecnou metodu pro odvození asymptotického řešení pro libovolný počet hier- archií narušení replikové symetrie. Pro oba modely hledáme řešení v blízkosti kritického bodu v nulovém vnějším poli a pro SK model též v nenulovém vnějším poli v blízkosti Almeida-Thoulessově linii nestability. Ukážeme, že pro SK model jsou všechna řešení s konečným počtem hierarchií nestabilní a že pouze řešení s nekonečně mnoha hierarchiemi je marginálně stabilní ve skelné fázi. U Pottsova skla najdeme navíc jednokrokové lokálně stabilní řešení koexistující s marginálně stabilním řešením s nekonečně mnoha hierarchiemi pro p > p∗ ≈ 2.82. Ukáže se, že lokálně stabilní řešení má menší volnou energii než druhé marginálně stabilní řešení. 1
|
|
|
Statistical Physics of Hard Optimization Problems
Zdeborová, Lenka ; Janiš, Václav (vedoucí práce) ; Mertens, Stephan (oponent) ; Zecchina, Riccardo (oponent)
Optimization is fundamental in many areas of science, from computer science and information theory to engineering and statistical physics, as well as to biology or social sciences. It typically involves a large number of variables and a cost function depending on these variables. Optimization problems in the NP-complete class are particularly dicult, it is believed that the number of operations required to minimize the cost function is in the most dicult cases exponential in the system size. However, even in an NP-complete problem the practically arising instances might, in fact, be easy to solve. The principal question we address in this thesis is: How to recognize if an NP-complete constraint satisfaction problem is typically hard and what are the main reasons for this? We adopt approaches from the statistical physics of disordered systems, in particular the cavity method developed originally to describe glassy systems. We describe new properties of the space of solutions in two of the most studied constraint satisfaction problems - random satisability and random graph coloring. We suggest a relation between the existence of the so-called frozen variables and the algorithmic hardness of a problem. Based on these insights, we introduce a new class of problems which we named "locked" constraint...
|
host ::
RSS.