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 NP-Complete 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: Order-to-chaos transition in the hardness of random Boolean satisfiability problems Melinda Varga, Robert Sumi, Maria Ercsey-Ravasz, 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 second-order phase transition at $\alpha_c$ in the random 3-SAT ensemble where dynamical trajectories become transiently chaotic, however, such transition does not occur for 2-SAT. This behavior also implies a novel type of transient chaos in which the escape rate has an exponential-algebraic dependence on the critical parameter. We demonstrate that the transition is generated by the appearance of non-solution 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 large-scale simulations of the three-dimensional 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 Munoz-Bauza, Andrew J. Ochoa, Wenlong Wang, Zheng Zhu Surprisingly often. Based on previous results of a large-scale numerical study of the equilibrium three-dimensional Edwards-Anderson Ising spin glass where it was demonstrated that autocorrelation times are directly correlated with the roughness of the free-energy landscape [Phys. Rev. E 87, 012104 (2013)], we show that a generalized spin-glass 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 order-parameter distribution does mirror salient features in the free-energy landscape of complex systems for moderate system sizes. [Preview Abstract] |
Friday, March 18, 2016 12:03PM - 12:15PM |
Y43.00005: TemperSAT: A new efficient fair-sampling random k-SAT 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 NP-hard constraint-satisfaction 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 state-of-the-art 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 NP-complete Problems Zheng Zhu, Chao Fang, Helmut G. Katzgraber NP-complete optimization problems with Boolean variables are of fundamental importance in computer science, mathematics and physics. Most notably, the minimization of general spin-glass-like 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 rejection-free 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 NP-complete optimization problems with Boolean variables. The cluster updates allow for a wide-spread sampling of phase space, thus speeding up optimization. By carefully tuning the pseudo-temperature (needed to randomize the configurations) of the problem, we show that the method can efficiently tackle problems on topologies with a large site-percolation threshold. We illustrate the ICANP2 heuristic on paradigmatic optimization problems, such as the satisfiability problem and the vertex cover problem. [Preview Abstract] |
Friday, March 18, 2016 12:27PM - 12:39PM |
Y43.00007: ABSTRACT WITHDRAWN |
Friday, March 18, 2016 12:39PM - 12:51PM |
Y43.00008: Lower-Critical Spin-Glass Dimension from 23 Sequenced Hierarchical Models Mehmet Demirtas, Asli Tuncer, A. Nihat Berker The lower-critical dimension for the existence of the Ising spin-glass 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$) near-linear fit to 23 different diminishing fractional dimensions. To obtain this result, the phase transition temperature between the disordered and spin-glass phases, the corresponding critical exponent $y_T$, and the runaway exponent $y_R$ of the spin-glass 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 Spin-Glass 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 renormalization-group theory, for odd $q$-state clock spin-glass models in $d=3$ dimensions [1]. These models exhibit asymmetric phase diagrams, as is also the case for quantum Heisenberg spin-glass models. No finite-temperature spin-glass 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 low-temperature portions of the phase diagrams and occur for $5 \leq q \leq15$. All algebraically ordered phases have the same structure, determined by an attractive finite-temperature sink fixed point where a dominant and a subdominant pair states have the only non-zero Boltzmann weights. The phase transition critical exponents quickly saturate to the high $q$ value as previously observed for even q-state 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 order-4 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 three-state Potts Field Theory Sergei Rutkevich Kink topological excitations are quite common in one-dimensional quantum ferromagnetic systems with the spontaneously broken discrete symmetry. Application of the external magnetic field $h$ induces the long-range attractive force between kinks leading to their confinement. While in the Ising Field Theory the particle sector in the confinement regime contains only the two-kink bound states ("the mesons"), in the three-state Potts Field Theory (PFT) the three-kink 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 quantum-mechanical problem for two non-relativistic particles interacting with a linear attractive potential, and my means of the WKB method. The masses of lightest baryons in the three-state PFT were calculated by the numerical solution of a three-particle quantum-mechanical 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 non-profit membership organization working to advance the knowledge of physics. |
© 2024 American Physical Society
| All rights reserved | Terms of Use
| Contact Us
Headquarters
1 Physics Ellipse, College Park, MD 20740-3844
(301) 209-3200
Editorial Office
100 Motor Pkwy, Suite 110, Hauppauge, NY 11788
(631) 591-4000
Office of Public Affairs
529 14th St NW, Suite 1050, Washington, D.C. 20045-2001
(202) 662-8700