Linear phase transition in random linear constraint satisfaction problems

Our model is a generalized linear programming relaxation of a much studied random K-SAT problem. Specifically, a set of linear constraints on K variables is fixed. From a pool of n variables, K variables are chosen uniformly at random and a constraint is chosen from also uniformly at random. This procedure is repeated m times independently. We are interested in whether the resulting linear programming problem is feasible. We prove that the feasibility property experiences a linear phase transition, when n and m = cn for a constant c. Namely, there exists a critical value c^* such that, when c < c^*, the problem is feasible or is asymptotically almost feasible, as n, but, when c>c^*, the distance to feasibility is at least a positive constant independent of n. Our result is obtained using the combination of a powerful local weak convergence method developed in Aldous [Ald92], [Ald01], Aldous and Steele [AS03], Steele [Ste02] and martingale techniques. By exploiting a linear programming duality, our theorem implies the following result in the context of sparse random graphs G(n, cn) on n nodes with cn edges, where edges are equipped with randomly generated weights. Let (n, c) denote maximum weight matching in G(n, cn). We prove that when c is a constant and n , the limit lim_n (n, c)/n, exists, with high probability. We further extend this result to maximum weight b-matchings also in G(n, cn).     

The K-SAT Problem in a Simple Limit

In this work we compute the thermodynamic properties of the 3-satisfiability problem in the infinite connectivity limit. In this limit the computation can be strongly simplified and the thermodynamic properties can be obtained with a high accuracy. We find evidence for a continuous replica symmetry breaking in the region of high number of clauses, >_c.     

长程阻错的统计物理理论

一个无序自旋玻璃系统可能有许许多多能量最小态或基态构型．有些格点的自旋可能在所有这些基态中都只取同一个值（这种情况称为自旋凝固）．也有另外一种情况出现，即某些格点在一部分基态中自旋取向上而在其余的基态中自旋向下；这样的格点称为未凝固的格点．本文的工作表明，2个或多个未凝固的格点，虽然每个格点的自旋都随着基态的不同而改变，但是有可能某一些特定的自旋取向组合不会出现于任何一基态构型中．这种现象称为长程阻错．本文提出一个新的长程阻错序参量R来定量刻划这种现象，并将这一统计物理理论用于图的最小覆盖和K—SAT等组合优化问题．