Abstract:
We study an exactly solvable version of the famous random Boolean satisfiability problem, the so called random XOR-SAT problem. Rare events are shown to affect the combinatorial ``phase diagram'' leading to a coexistence of solvable and unsolvable instances of the combinatorial problem in a certain region of the parameters characterizing the model. Such instances differ by a non-extensive quantity in the ground state energy of the associated diluted spin-glass model. We also show that the critical exponent $\nu$, controlling the size of the critical window where the probability of having solutions vanishes, depends on the model parameters, shedding light on the link between random hyper-graph topology and universality classes. In the case of random satisfiability, a similar behavior was conjectured to be connected to the onset of computational intractability.

Abstract:
We study a simple and exactly solvable model for the generation of random satisfiability problems. These consist of $\gamma N$ random boolean constraints which are to be satisfied simultaneously by $N$ logical variables. In statistical-mechanics language, the considered model can be seen as a diluted p-spin model at zero temperature. While such problems become extraordinarily hard to solve by local search methods in a large region of the parameter space, still at least one solution may be superimposed by construction. The statistical properties of the model can be studied exactly by the replica method and each single instance can be analyzed in polynomial time by a simple global solution method. The geometrical/topological structures responsible for dynamic and static phase transitions as well as for the onset of computational complexity in local search method are thoroughly analyzed. Numerical analysis on very large samples allows for a precise characterization of the critical scaling behaviour.

Abstract:
There exists an exact relationship between the quasi-exactly solvable problems of quantum mechanics and models of square and rectangular random complex matrices. This relationship enables one to reduce the problem of constructing topological ($1/N$) expansions in random matrix models to the problem of constructing semiclassical expansions for observables in quasi-exactly solvable problems. Lie algebraic aspects of this relationship are also discussed.

Abstract:
In this note I will review some of the recent results that have been obtained in the probabilistic approach to the random satisfiability problem. At the present moment the results are only heuristic. In the case of the random 3-satisfiability problem a phase transition from the satisfiable to the unsatisfiable phase is found at $\alpha=4.267$. There are other values of $\alpha$ that separates different regimes and they will be described in details. In this context the properties of the survey decimation algorithm will also be discussed.

Abstract:
How can we remove some interactions in a constraint satisfaction problem (CSP) such that it still remains satisfiable? In this paper we study a modified survey propagation algorithm that enables us to address this question for a prototypical CSP, i.e. random K-satisfiability problem. The average number of removed interactions is controlled by a tuning parameter in the algorithm. If the original problem is satisfiable then we are able to construct satisfiable subproblems ranging from the original one to a minimal one with minimum possible number of interactions. The minimal satisfiable subproblems will provide directly the solutions of the original problem.

Abstract:
Using elementary rigorous methods we prove the existence of a clustered phase in the random $K$-SAT problem, for $K\geq 8$. In this phase the solutions are grouped into clusters which are far away from each other. The results are in agreement with previous predictions of the cavity method and give a rigorous confirmation to one of its main building blocks. It can be generalized to other systems of both physical and computational interest.

Abstract:
We determine the exact threshold of satisfiability for random instances of a particular NP-complete constraint satisfaction problem (CSP). This is the first random CSP model for which we have determined a precise linear satisfiability threshold, and for which random instances with density near that threshold appear to be computationally difficult. More formally, it is the first random CSP model for which the satisfiability threshold is known and which shares the following characteristics with random k-SAT for k >= 3. The problem is NP-complete, the satisfiability threshold occurs when there is a linear number of clauses, and a uniformly random instance with a linear number of clauses asymptotically almost surely has exponential resolution complexity.

Abstract:
We consider the random regular $k$-NAE-SAT problem with $n$ variables each appearing in exactly $d$ clauses. For all $k$ exceeding an absolute constant $k_0$, we establish explicitly the satisfiability threshold $d_*=d_*(k)$. We prove that for $dd_*$ the problem is unsatisfiable with high probability. If the threshold $d_*$ lands exactly on an integer, we show that the problem is satisfiable with probability bounded away from both zero and one. This is the first result to locate the exact satisfiability threshold in a random constraint satisfaction problem exhibiting the condensation phenomenon identified by Krzakala et al. (2007). Our proof verifies the one-step replica symmetry breaking formalism for this model. We expect our methods to be applicable to a broad range of random constraint satisfaction problems and combinatorial problems on random graphs.

Abstract:
We propose a model for two $(d+1)$-dimensional directed polymers subjected to a mutual $\delta$-function interaction with a random coupling constant, and present an exact renormalization group study for this system. The exact $\beta$-function, evaluated through an $\epsilon(=1-d)$ expansion for second and third moments of the partition function, exhibits the marginal relevance of the disorder at $d=1$, and the presence of a phase transition from a weak to strong disorder regime for $d>1$. The lengthscale exponent for the critical point is $\nu=1/2\mid\epsilon\mid$. We give details of the renormalization. We show that higher moments do not require any new interaction, and hence the $\beta$ function remains the same for all moments. The method is extended to multicritical systems involving an $m$ chain interaction. The corresponding disorder induced phase transition for $d>d_m=1/(m-1)$ has the critical exponent ${\nu}_m=[2d(m-1)-2]^{-1}$. For both the cases, an essential singularity appears for the lengthscale right at the upper critical dimension $d_m$. We also discuss the strange behavior of an annealed system with more than two chains with pairwise random interactions among each other.

Abstract:
In this paper we quantize the $N$-dimensional classical Hamiltonian system $H= \frac{|q|}{2(\eta + |q|)} p^2-\frac{k}{\eta +|q|}$, that can be regarded as a deformation of the Coulomb problem with coupling constant $k$, that it is smoothly recovered in the limit $\eta\to 0$. Moreover, the kinetic energy term in $H$ is just the one corresponding to an $N$-dimensional Taub-NUT space, a fact that makes this system relevant from a geometric viewpoint. Since the Hamiltonian $H$ is known to be maximally superintegrable, we propose a quantization prescription that preserves such superintegrability in the quantum mechanical setting. We show that, to this end, one must choose as the kinetic part of the Hamiltonian the conformal Laplacian of the underlying Riemannian manifold, which combines the usual Laplace-Beltrami operator on the Taub-NUT manifold and a multiple of its scalar curvature. As a consequence, we obtain a novel exactly solvable deformation of the quantum Coulomb problem, whose spectrum is computed in closed form for positive values of $\eta$ and $k$, and showing that the well-known maximal degeneracy of the flat system is preserved in the deformed case. Several interesting algebraic and physical features of this new exactly solvable quantum system are analysed, and the quantization problem for negative values of $\eta$ and/or $k$ is also sketched.