PubMed Health⌕ Search

Biomedical subjects

A K Hartmann

Publications and source records attributed to A K Hartmann.

10 recordsLinked to original sources
PubMed2003

Corrections to scaling are large for droplets in two-dimensional spin glasses.

The energy of a droplet of linear extent l in the droplet theory of spin glasses goes as l(theta) for large l. It is shown by numerical studies of large droplets in two-dimensional systems that this formula needs to be modified by the addition of a scaling correction l(-omega) in order to accurately describe droplet energies at the length scales currently probed in numerical simulations. Using this simple modification, it is now possible to explain many results which have been found in simulations of three-dimensional Ising spin glasses with the droplet model.

Journal Article↗
PubMed2002

Hiding solutions in random satisfiability problems: a statistical mechanics approach.

A major problem in evaluating stochastic local search algorithms for NP-complete problems is the need for a systematic generation of hard test instances having previously known properties of the optimal solutions. On the basis of statistical mechanics results, we propose random generators of hard and satisfiable instances for the 3-satisfiability problem. The design of the hardest problem instances is based on the existence of a first order ferromagnetic phase transition and the glassy nature of excited states. The analytical predictions are corroborated by numerical results obtained from complete as well as stochastic local algorithms.

Algorithms↗
PubMed2001

Stress relaxation of near-critical gels.

The time-dependent stress relaxation for a Rouse model of a cross-linked polymer melt is completely determined by the spectrum of eigenvalues of the connectivity matrix. The latter has been computed analytically for a mean-field distribution of cross-links. It shows a Lifshitz tail for small eigenvalues and all concentrations below the percolation threshold, giving rise to a stretched exponential decay of the stress relaxation function in the sol phase. At the critical point the density of states is finite for small eigenvalues, resulting in a logarithmic divergence of the viscosity and an algebraic decay of the stress relaxation function. Numerical diagonalization of the connectivity matrix supports the analytical findings and has furthermore been applied to cluster statistics corresponding to random bond percolation in two and three dimensions.

Journal Article↗
PubMed2001

Minimal vertex covers on finite-connectivity random graphs: a hard-sphere lattice-gas picture.

The minimal vertex-cover (or maximal independent-set) problem is studied on random graphs of finite connectivity. Analytical results are obtained by a mapping to a lattice gas of hard spheres of (chemical) radius 1, and they are found to be in excellent agreement with numerical simulations. We give a detailed description of the replica-symmetric phase, including the size and entropy of the minimal vertex covers, and the structure of the unfrozen component which is found to percolate at a connectivity c approximately 1.43. The replica-symmetric solution breaks down at c=e approximately 2.72. We give a simple one-step replica-symmetry-broken solution, and discuss the problems in the interpretation and generalization of this solution.

Journal Article↗
PubMed2001

Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs.

We analytically describe the typical solution time needed by a backtracking algorithm to solve the vertex-cover problem on finite-connectivity random graphs. We find two different transitions: The first one is algorithm dependent and marks the dynamical transition from linear to exponential solution times. The second one gives the maximum computational complexity, and is found exactly at the threshold where the system undergoes an algorithm-independent phase transition in its solvability. Analytical results are corroborated by numerical simulations.

Journal Article↗
PubMed2000

Ground-state clusters of two-, three-, and four-dimensional +/-J Ising spin glasses.

A huge number of independent true ground-state configurations is calculated for two-, three- and four-dimensional +/-J spin-glass models. Using the genetic cluster-exact approximation method, system sizes up to N=20(2),8(3),6(4) spins are treated. A "ballistic-search" algorithm is applied, which allows even for large system sizes to identify clusters of ground states that are connected by chains of zero-energy flips of spins. The number of clusters n(C) diverges with N going to infinity. For all dimensions considered here, an exponential increase of n(C) appears to be more likely than a growth with a power of N. The number of different ground states is found to grow clearly exponentially with N. A zero-temperature entropy per spin of s(0)=0.078(5)k(B) (2D), s(0)=0.051(3)k(B) (3D), respectively, s(0)=0.027(5)k(B) (4D) is obtained.

Journal Article↗
PubMed2000

Number of guards needed by a museum: a phase transition in vertex covering of random graphs.

In this Letter we study the NP-complete vertex cover problem on finite connectivity random graphs. When the allowed size of the cover set is decreased, a discontinuous transition in solvability and typical-case complexity occurs. This transition is characterized by means of exact numerical simulations as well as by analytical replica calculations. The replica symmetric phase diagram is in excellent agreement with numerical findings up to average connectivity e, where replica symmetry becomes locally unstable.

Journal Article↗
PubMed1999

Calculation of ground states of four-dimensional +/-J Ising spin glasses.

Ground states of four-dimensional (d=4) Edwards-Anderson Ising spin glasses are calculated for sizes up to 7 x 7 x 7 x 7 using a combination of a genetic algorithm and cluster-exact approximation. The ground-state energy of the infinite system is extrapolated as e0(infinity)=-2.095(1). The ground-state stiffness (or domain wall) energy Delta is calculated. A delta approximately L(theta(S)) behavior with theta(S)=0.64(5) is found which confirms that the d=4 model has an equilibrium spin-glass-paramagnet transition for nonzero T(c).

Journal Article↗