Bulletin of the American Physical Society
APS March Meeting 2016
Volume 61, Number 2
Monday–Friday, March 14–18, 2016; Baltimore, Maryland
Session Y43: Statistical Mechanics of Frustrated Systems, Including Constraint Satisfaction, Satisfiability and NPComplete Problems 
Hide Abstracts 
Sponsoring Units: GSNP Chair: Jonathsan Machta, University of Massachusetts, Amherst Room: 346 
Friday, March 18, 2016 11:15AM  11:27AM 
Y43.00001: Ordertochaos transition in the hardness of random Boolean satisfiability problems Melinda Varga, Robert Sumi, Maria ErcseyRavasz, Zoltan Toroczkai Transient chaos is a phenomenon characterizing the dynamics of phase space trajectories evolving towards an attractor in physical systems. We show that transient chaos also appears in the dynamics of certain algorithms searching for solutions of constraint satisfaction problems (e.g., Sudoku). We present a study of the emergence of hardness in Boolean satisfiability ($k$SAT) using an analog deterministic algorithm. Problem hardness is defined through the escape rate $\kappa$, an invariant measure of transient chaos, and it expresses the rate at which the trajectory approaches a solution. We show that the hardness in random $k$SAT ensembles has a wide variation approximable by a lognormal distribution. We also show that when increasing the density of constraints $\alpha$, hardness appears through a secondorder phase transition at $\alpha_c$ in the random 3SAT ensemble where dynamical trajectories become transiently chaotic, however, such transition does not occur for 2SAT. This behavior also implies a novel type of transient chaos in which the escape rate has an exponentialalgebraic dependence on the critical parameter. We demonstrate that the transition is generated by the appearance of nonsolution basins in the solution space as the density of constraints is increased. [Preview Abstract] 
Friday, March 18, 2016 11:27AM  11:39AM 
Y43.00002: Population Annealing: Theory and Application in Spin Glasses Jonathan Machta, Wenlong Wang, Helmut G. Katzgraber Population annealing is an efficient sequential Monte Carlo algorithm for simulating equilibrium states of systems with rough free energy landscapes. The theory of population annealing is presented, and systematic and statistical errors are discussed. The behavior of the algorithm is studied in the context of largescale simulations of the threedimensional Ising spin glass and the performance of the algorithm is compared to parallel tempering. It is found that the two algorithms are similar in efficiency though with different strengths and weaknesses. [Preview Abstract] 
Friday, March 18, 2016 11:39AM  11:51AM 
Y43.00003: Bond and temperature chaos in spin glasses revealed through thermal boundary conditions Wenlong Wang Spin glasses are complex systems with rugged energy landscapes that exhibit chaotic behavior. Unfortunately, despite decades of study, there is still no clear understanding of the chaotic behavior found in these systems. The use of thermal boundary conditions has become a useful approach to study such phenomena. Here we discuss how to efficiently simulate bond and temperature chaos using thermal boundary conditions and population annealing Monte Carlo. We provide a simple scaling argument for bond and temperature chaos, and present numerical results of the scaling exponents. Similarities and differences of bond chaos and temperature chaos are also discussed. [Preview Abstract] 
Friday, March 18, 2016 11:51AM  12:03PM 
Y43.00004: Can we predict the difficulty of optimization problems without solving them? Helmut G. Katzgraber, Chao Fang, Richard Lawrence, Oliver Melchert, Humberto MunozBauza, Andrew J. Ochoa, Wenlong Wang, Zheng Zhu Surprisingly often. Based on previous results of a largescale numerical study of the equilibrium threedimensional EdwardsAnderson Ising spin glass where it was demonstrated that autocorrelation times are directly correlated with the roughness of the freeenergy landscape [Phys. Rev. E 87, 012104 (2013)], we show that a generalized spinglass order parameter can be used as a proxy to the computational difficulty of various paradigmatic optimization problems. Our results are illustrated with different optimization algorithms, as well as optimization problems. Furthermore, we show numerical evidence that the orderparameter distribution does mirror salient features in the freeenergy landscape of complex systems for moderate system sizes. [Preview Abstract] 
Friday, March 18, 2016 12:03PM  12:15PM 
Y43.00005: TemperSAT: A new efficient fairsampling random kSAT solver Chao Fang, Zheng Zhu, Helmut G. Katzgraber The set membership problem is of great importance to many applications and, in particular, database searches for target groups. Recently, an approach to speed up set membership searches based on the NPhard constraintsatisfaction problem (random $k$SAT) has been developed [S.~Weaver {\em et al.}~JSAT 8, 129 (2014)]. However, the bottleneck of the approach lies in finding the solution to a large SAT formula efficiently and, in particular, a large number of independent solutions is needed to reduce the probability of false positives. Unfortunately, traditional random $k$SAT solvers such as WalkSAT are biased when seeking solutions to the Boolean formulas. By porting parallel tempering Monte Carlo to the sampling of binary optimization problems, we introduce a new algorithm (TemperSAT) whose performance is comparable to current stateoftheart SAT solvers for large $k$ with the added benefit that theoretically it can find many independent solutions quickly. We illustrate our results by comparing to the currently fastest implementation of WalkSAT, WalkSAT{\em lm}. [Preview Abstract] 
Friday, March 18, 2016 12:15PM  12:27PM 
Y43.00006: ICANP2: Isoenergetic cluster algorithm for NPcomplete Problems Zheng Zhu, Chao Fang, Helmut G. Katzgraber NPcomplete optimization problems with Boolean variables are of fundamental importance in computer science, mathematics and physics. Most notably, the minimization of general spinglasslike Hamiltonians remains a difficult numerical task. There has been a great interest in designing efficient heuristics to solve these computationally difficult problems. Inspired by the rejectionfree isoenergetic cluster algorithm developed for Ising spin glasses [Phys.~Rev.~Lett.~115, 077201 (2015)], we present a generalized cluster update that can be applied to different NPcomplete optimization problems with Boolean variables. The cluster updates allow for a widespread sampling of phase space, thus speeding up optimization. By carefully tuning the pseudotemperature (needed to randomize the configurations) of the problem, we show that the method can efficiently tackle problems on topologies with a large sitepercolation threshold. We illustrate the ICANP2 heuristic on paradigmatic optimization problems, such as the satisfiability problem and the vertex cover problem. [Preview Abstract] 

Y43.00007: ABSTRACT WITHDRAWN 
Friday, March 18, 2016 12:39PM  12:51PM 
Y43.00008: LowerCritical SpinGlass Dimension from 23 Sequenced Hierarchical Models Mehmet Demirtas, Asli Tuncer, A. Nihat Berker The lowercritical dimension for the existence of the Ising spinglass phase is calculated, numerically exactly, as $d_L = 2.520$ for a sequence of hierarchical lattices, from an essentially exact (correlation coefficent $R^2 = 0.999999$) nearlinear fit to 23 different diminishing fractional dimensions. To obtain this result, the phase transition temperature between the disordered and spinglass phases, the corresponding critical exponent $y_T$, and the runaway exponent $y_R$ of the spinglass phase are calculated for consecutive hierarchical lattices as dimension is lowered.[1] \\[4pt] [1] M. Demirtas, A. Tuncer, and A.N. Berker, Phys. Rev. E 92, 022136 (2015). [Preview Abstract] 
Friday, March 18, 2016 12:51PM  1:03PM 
Y43.00009: Odd $\textbf{q}$State Clock SpinGlass Models in Three Dimensions, Asymmetric Phase Diagrams, and Multiple Algebraically Ordered Phases Efe Ilker, A. Nihat Berker Distinctive orderings and phase diagram structures are found, from renormalizationgroup theory, for odd $q$state clock spinglass models in $d=3$ dimensions [1]. These models exhibit asymmetric phase diagrams, as is also the case for quantum Heisenberg spinglass models. No finitetemperature spinglass phase occurs. For all odd $q\geq 5$, algebraically ordered antiferromagnetic phases [2,3] occur. One such phase is dominant and occurs for all $q\geq 5$. Other such phases occupy small lowtemperature portions of the phase diagrams and occur for $5 \leq q \leq15$. All algebraically ordered phases have the same structure, determined by an attractive finitetemperature sink fixed point where a dominant and a subdominant pair states have the only nonzero Boltzmann weights. The phase transition critical exponents quickly saturate to the high $q$ value as previously observed for even qstate clock models [4]. \\[4pt] [1] E. Ilker and A. N. Berker, Phys. Rev. E {\bf 90}, 062112 (2014) \\[4pt] [2] A. N. Berker and L. P. Kadanoff, J. Phys. A {\bf 13}, L259 (1980) \\[4pt] [3] A. N. Berker and L. P. Kadanoff, J. Phys. A {\bf 13}, 3786 (1980) \\[4pt] [4] E. Ilker and A. N. Berker, Phys. Rev. E {\bf 87}, 032124 (2013) [Preview Abstract] 
Friday, March 18, 2016 1:03PM  1:15PM 
Y43.00010: Spinodals of the Ising model on the order4 pentagonal tiling of the hyperbolic plane Howard L. Richards In the Euclidean plane, the Ising model on a regular lattice does not have a true spinodal  that is, there is no local minimum of the free energy that persists forever (in the limit of infinitely large systems) except for the global minimum, which characterizes the stable state. However, a local minimum can persist for a very long time, so the minimum can be referred to as a ``metastable'' state. The manner in which the metastable state decays depends on the strength of the magnetic field and the system size; the ``thermodynamic spinodal'' is the transition between systems large enough to contain a single critical droplet and systems that are too small to do so, and the ``dynamic spinodal'' marks the transition between decay as a Poisson process to decay that is ``deterministic'', meaning the standard deviation of the lifetime of the metastable state is small compared with its mean value. However, in the hyperbolic plane, true metastability exists, and evidence shows that the thermodynamic spinodal and dynamic spinodal are numerically close to the true spinodal, the field below which the metastable state cannot decay through the nucleation and growth of droplets. [Preview Abstract] 
Friday, March 18, 2016 1:15PM  1:27PM 
Y43.00011: Weak confinement in the threestate Potts Field Theory Sergei Rutkevich Kink topological excitations are quite common in onedimensional quantum ferromagnetic systems with the spontaneously broken discrete symmetry. Application of the external magnetic field $h$ induces the longrange attractive force between kinks leading to their confinement. While in the Ising Field Theory the particle sector in the confinement regime contains only the twokink bound states ("the mesons"), in the threestate Potts Field Theory (PFT) the threekink bound states ("the baryons") can exist as well. In the weak confinement regime, which is realized at small external magnetic fields, the meson masses in the PFT can be determined analytically in the leading order in $h$ by means of the solution of a quantummechanical problem for two nonrelativistic particles interacting with a linear attractive potential, and my means of the WKB method. The masses of lightest baryons in the threestate PFT were calculated by the numerical solution of a threeparticle quantummechanical problem. The obtained mass spectra for the PFT mesons and baryons were confirmed recently by Lenc\'es and Tak\'acs in numerical calculations based on the truncated conformal space approach. [Preview Abstract] 
Follow Us 
Engage
Become an APS Member 
My APS
Renew Membership 
Information for 
About APSThe American Physical Society (APS) is a nonprofit membership organization working to advance the knowledge of physics. 
© 2019 American Physical Society
 All rights reserved  Terms of Use
 Contact Us
Headquarters
1 Physics Ellipse, College Park, MD 207403844
(301) 2093200
Editorial Office
1 Research Road, Ridge, NY 119612701
(631) 5914000
Office of Public Affairs
529 14th St NW, Suite 1050, Washington, D.C. 200452001
(202) 6628700