BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Stefan Boettcher

Stefan Boettcher appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
cond-mat.dis-nncond-mat.stat-mechquant-phcond-mat.softmath.OCArtificial Intelligencecond-matDiscrete Mathematicshep-latphysics.soc-phComputational Complexitycond-mat.mtrl-scihep-thMachine Learningmath.CONetworking and Internet Architecturephysics.comp-phPopulations and Evolution

Catalog footprint

What is connected

32works
18topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

32 published item(s)

preprint2026arXiv

Instability cascades in crumpling mylar sheets follow a log-Poisson statistic

The process of aging following a hard quench into a glassy state is characterized universally, for a wide class of materials, by logarithmic evolution of state variables and a power-law decay of two-time correlation functions that collapse only for the ratio of those times. This stands in stark contrast with relaxation in equilibrium materials, where time-translational invariance holds. It is by now widely recognized that these aging processes, which ever so slowly relax a complex disordered material after a quench, are facilitated by activated events. Yet, theories often cited to describe such a non-equilibrium process can be shown to miss pertinent aspects that are inherent to many experiments. A case in point are recent experiments on crumpling sheets of mylar loaded by a weight whose acoustic emissions are measured while the material buckles. Using extensive simulations to generate long time-series of such buckling events, we show that crumpling is a log-Poisson process activated by increasingly rare record-sized fluctuations in a slowly stiffening material characterized by a logarithmically growing length-scale. Crumpling thus adds to a range of glassy materials exhibiting the log-Poisson property, which can be used to discriminate between theories.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Density Fluctuations in Granular Piles Traversing the Glass Transition: A Grain-Scale Characterization of the Transition via the Internal Energy

The transition into a glassy state of the ensemble of static, mechanically stable configurations of a tapped granular pile is explored using extensive molecular dynamics simulations. We show that different horizontal sub-regions ("layers") along the height of the pile traverse this transition in a similar manner but at distinct tap intensities. We supplement the conventional approach based purely on properties of the static configurations with investigations of the grain-scale dynamics by which the tap energy is transmitted throughout the pile. We find that the effective energy that particles dissipate is a function of each particle's location in the pile and, moreover, that its value plays a distinctive role in the transformation between configurations. This internal energy provides a "temperature-like" parameter that allows us to align the transition into the glassy state for all layers, as well as different annealing schedules, at a critical value.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems like Max-Cut

In Nature Machine Intelligence 4, 367 (2022), Schuetz et al provide a scheme to employ graph neural networks (GNN) as a heuristic to solve a variety of classical, NP-hard combinatorial optimization problems. It describes how the network is trained on sample instances and the resulting GNN heuristic is evaluated applying widely used techniques to determine its ability to succeed. Clearly, the idea of harnessing the powerful abilities of such networks to ``learn'' the intricacies of complex, multimodal energy landscapes in such a hands-off approach seems enticing. And based on the observed performance, the heuristic promises to be highly scalable, with a computational cost linear in the input size $n$, although there is likely a significant overhead in the pre-factor due to the GNN itself. However, closer inspection shows that the reported results for this GNN are only minutely better than those for gradient descent and get outperformed by a greedy algorithm, for example, for Max-Cut. The discussion also highlights what I believe are some common misconceptions in the evaluations of heuristics.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Transport and Localization in Quantum Walks on a Random Hierarchy of Barriers

We study transport within a spatially heterogeneous one-dimensional quantum walk with a combination of hierarchical and random barriers. Recent renormalization group calculations for a spatially disordered quantum walk with a regular hierarchy of barriers alone have shown a gradual decrease in transport but no localization for increasing (but finite) barrier sizes. In turn, it is well-known that extensive random disorder in the spatial barriers is sufficient to localize a quantum walk on the line. Here we show that adding only a sparse (sub-extensive) amount of randomness to a hierarchy of barriers is sufficient to induce localization such that transport ceases. Our numerical results suggest the existence of a localization transition for a combination of both, the strength of the regular barrier hierarchy at large enough randomness as well as the increasing randomness at sufficiently strong barriers in the hierarchy.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Analysis of landscape hierarchy during coarsening and aging in Ising spin glasses

We use record dynamics (RD), a coarse-grained description of the ubiquitous relaxation phenomenology known as "aging", as a diagnostic tool to find universal features that distinguish between the energy landscapes of Ising spin models and the ferromagnet. According to RD, a non-equilibrium system after a quench relies on fluctuations that randomly generate a sequence of irreversible record-sized events (quakes or avalanches) that allow the system to escape ever-higher barriers of meta-stable states within a complex, hierarchical energy landscape. Once these record events allow the system to overcome such barriers, the system relaxes by tumbling into the following meta-stable state that is marginally more stable. Within this framework, a clear distinction can be drawn between the coarsening dynamics of an Ising ferromagnet and the aging of the spin glass, which are often put in the same category. To that end, we interpolate between the spin glass and ferromagnet by varying the admixture $p$ of ferromagnetic over anti-ferromagnetic bonds from the glassy state (at 50% each) to wherever clear ferromagnetic behavior emerges. The accumulation of record events grows logarithmic with time in the glassy regime, with a sharp transition at a specific admixture into the ferromagnetic regime where such activations saturate quickly. We show this effect both for the Edwards-Anderson model on a cubic lattice as well as the Sherrington-Kirkpatrick (mean-field) spin glass. While this transition coincides with a previously observed zero-temperature equilibrium transition in the former, that transition has not yet been described for the latter.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Ground State Properties of the Diluted Sherrington-Kirkpatrick Spin Glass

We present a numerical study of ground states of the dilute versions of the Sherrington-Kirkpatrick (SK) mean-field spin glass. In contrast to so-called "sparse" mean-field spin glasses that have been studied widely on random networks of finite (average or regular) degree, the networks studied here are randomly bond-diluted to an overall density $p$, such that the average degree diverges as $\sim pN$ with the system size $N$. Ground-state energies are obtained with high accuracy for random instances over a wide range of fixed $p$. Since this is a NP-hard combinatorial problem, we employ the Extremal Optimization heuristic to that end. We find that the exponent describing the finite-size corrections, $ω$, varies continuously with $p$, a somewhat surprising result, as one would not expect that gradual bond-dilution would change the $T=0$ universality class of a statistical model. For $p\to1$, the familiar result of $ω(p=1)\approx\frac{2}{3}$ for SK is obtained.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Quantum Ultra-Walks: Walks on a Line with Hierarchical Spatial Heterogeneity

We discuss the model of a one-dimensional, discrete-time walk on a line with spatial heterogeneity in the form of a variable set of ultrametric barriers. Inspired by the homogeneous quantum walk on a line, we develop a formalism by which the classical ultrametric random walk as well as the quantum walk can be treated in parallel by using a "coined" walk with internal degrees of freedom. For the random walk, this amounts to a $2^{\rm nd}$-order Markov process with a \emph{stochastic} coin, better known as an (anti-)persistent walk. When this coin varies spatially in the hierarchical manner of "ultradiffusion," it reproduces the well-known results of that model. The exact analysis employed for obtaining the walk dimension $d_{w}$, based on the real-space renormalization group (RG), proceeds virtually identical for the corresponding quantum walk with a $unitary$ coin. However, while the classical walk remains robustly diffusive ($d_{w}=\frac{1}{2}$) for a wide range of barrier heights, unitarity provides for a quantum walk dimension $d_{w}$ that varies continuously, for even the smallest amount of heterogeneity, from ballistic spreading ($d_{w}=1$) in the homogeneous limit to confinement ($d_{w}=\infty$) for diverging barriers. Yet for any $d_{w}<\infty$ the quantum ultra-walk never appears to localize.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Universal Features of Annealing and Aging in Compaction of Granular Piles

We explore the compaction dynamics of a granular pile after a hard quench from a liquid into the glassy regime. First, we establish that the otherwise athermal granular pile during tapping exhibits annealing behavior comparable to glassy polymer or colloidal systems. Like those other systems, the pile undergoes a glass transition and "freezes" into different non-equilibrium glassy states at low agitation for different annealing speeds, starting from the same initial equilibrium state at high agitation. Then, we quench the system instantaneously from the highly-agitated state to below the glass transition regime to study the ensuing aging dynamics. In this classical aging protocol, the density increases (i.e., the potential energy of the pile decreases) logarithmically over several decades in time. Instead of system-wide, thermodynamic measures, here we identify the intermittent, irreversible events ("quakes") that actually drive the glassy relaxation process. We find that the event rate decelerates hyperbolically, which explains the observed increase in density when the integrated contribution to the downward displacements is evaluated. We argue that such a hyperbolically decelerating event rate is consistent with a log-Poisson process, also found as a universal feature of aging in many thermal glasses.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Analysis of the Relation between Quadratic Unconstrained Binary Optimization (QUBO) and the Spin Glass Ground-State Problem

We analyze the transformation of QUBO from its conventional Boolean presentation into an equivalent spin glass problem with coupled $\pm1$ spin variables exposed to a site-dependent external field. We find that in a widely used testbed for QUBO these fields tend to be rather large compared to the typical coupling and many spins in each optimal configurations simply align with the fields irrespective of their constraints. Thereby, the testbed instances tend to exhibit large redundancies - seemingly independent variables which contribute little to the hardness of the problem, however. We demonstrate various consequences of this insight, for QUBO solvers as well as for heuristics developed for finding spin glass ground states. To this end, we implement the Extremal Optimization (EO) heuristic, in a new adaptation for the QUBO problem. We also propose a novel way to assess the quality of heuristics for increasing problem sizes based on asymptotic scaling.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Continuous-Time Quantum Search on Balanced Trees

We examine the effect of network heterogeneity on the performance of quantum search algorithms. To this end, we study quantum search on a tree for the oracle Hamiltonian formulation employed by continuous-time quantum walks. We use analytical and numerical arguments to show that the exponent of the asymptotic running time $\sim N^β$ changes uniformly from $β=0.5$ to $β=1$ as the searched-for site is moved from the root of the tree towards the leaves. These results imply that the time complexity of the quantum search algorithm on a balanced tree is closely correlated with certain path-based centrality measures of the searched-for site.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Record Dynamics in the Parking Lot Model

We present an analytical and numerical study of the parking lot model (PLM) of granular relaxation and make a connection to the aging dynamics of dense colloids. As we argue, the PLM is a Kinetically Constrained Model which features astronomically large equilibration times and displays a characteristic aging behavior on all observable time scales. The density of parked cars displays quasi-equilibrium Gaussian fluctuations interspersed by increasingly rare intermittent events, quakes, which can lead to an increase of the density to new record values. Defining active clusters as the shortest domains of parked cars which must be re-arranged to allow further insertions, we find that their typical length grows logarithmically with time for low enough temperatures and show how the number of active clusters on average gradually decreases as the system approaches equilibrium. We further characterize the aging process in terms of the statistics of the record sized fluctuations in the interstitial free volume which lead to quakes and show that quakes are uncorrelated and that they can be approximately described as a Poisson process in logarithmic time.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Record Dynamics: Direct Experimental Evidence from Jammed Colloids

In a broad class of complex materials a quench leads to a multi-scaled relaxation process known as aging. To explain its commonality and the astounding insensitivity to most microscopic details, record dynamics (RD) posits that a small set of increasingly rare and irreversible events, so called quakes, controls the dynamics. While key predictions of RD are known to concur with a number of experimental and simulational results, its basic assumption on the nature of quake statistics has proven extremely difficult to verify experimentally. The careful distinction of rare ("record") cage-breaking events from in-cage rattle accomplished in previous experiments on jammed colloids, enables us to extract the first direct experimental evidence for the fundamental hypothesis of RD that the rate of quakes decelerates with the inverse of the system age. The resulting description shows the predicted growth of the particle mean square displacement and of a mesoscopic lengthscale with the logarithm of time.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Classification of critical phenomena in hierarchical small-world networks

A classification of critical behavior is provided in systems for which the renormalization group equations are control-parameter dependent. It describes phase transitions in networks with a recursive, hierarchical structure but appears to apply also to a wider class of systems, such as conformal field theories. Although these transitions generally do not exhibit universality, three distinct regimes of characteristic critical behavior can be discerned that combine an unusual mixture of finite- and infinite-order transitions. In the spirit of Landau's description of a phase transition, the problem can be reduced to the local analysis of a cubic recursion equation, here, for the renormalization group flow of some generalized coupling. Among other insights, this theory explains the often-noted prevalence of the so-called inverted Berezinskii-Kosterlitz-Thouless transitions in complex networks. As a demonstration, a one-parameter family of Ising models on hierarchical networks is considered.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Jamming in Hierarchical Networks

We study the Biroli-Mezard model for lattice glasses on a number of hierarchical networks. These networks combine certain lattice-like features with a recursive structure that makes them suitable for exact renormalization group studies and provide an alternative to the mean-field approach. In our numerical simulations here, we first explore their equilibrium properties with the Wang-Landau algorithm. Then, we investigate their dynamical behavior using a grand-canonical annealing algorithm. We find that the dynamics readily falls out of equilibrium and jams in many of our networks with certain constraints on the neighborhood occupation imposed by the Biroli-Mezard model, even in cases where exact results indicate that no ideal glass transition exists. But while we find that time-scales for the jams diverge, our simulations cannot ascertain such a divergence for a packing fraction distinctly above random close packing. In cases where we allow hopping in our dynamical simulations, the jams on these networks generally disappear.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Real-Space Renormalization Group for Spectral Properties of Hierarchical Networks

We derive the determinant of the Laplacian for the Hanoi networks and use it to determine their number of spanning trees (or graph complexity) asymptotically. While spanning trees generally proliferate with increasing average degree, the results show that modifications within the basic patterns of design of these hierarchical networks can lead to significant variations in their complexity. To this end, we develop renormalization group methods to obtain recursion equations from which many spectral properties can be obtained. This provides the basis for future applications to explore the physics of several dynamic processes.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Relation between Random Walks and Quantum Walks

Based on studies on four specific networks, we conjecture a general relation between the walk dimensions $d_{w}$ of discrete-time random walks and quantum walks with the (self-inverse) Grover coin. In each case, we find that $d_{w}$ of the quantum walk takes on exactly half the value found for the classical random walk on the same geometry. Since walks on homogeneous lattices satisfy this relation trivially, our results for heterogeneous networks suggests that such a relation holds irrespective of whether translational invariance is maintained or not. To develop our results, we extend the renormalization group analysis (RG) of the stochastic master equation to one with a unitary propagator. As in the classical case, the solution $ρ(x,t)$ in space and time of this quantum walk equation exhibits a scaling collapse for a variable $x^{d_{w}}/t$ in the weak limit, which defines $d_{w}$ and illuminates fundamental aspects of the walk dynamics, e.g., its mean-square displacement. We confirm the collapse for $ρ(x,t)$ in each case with extensive numerical simulation. The exact values for $d_{w}$ in themselves demonstrate that RG is a powerful complementary approach to study the asymptotics of quantum walks that weak-limit theorems have not been able to access, such as for systems lacking translational symmetries beyond simple trees.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

From explosive to infinite-order transitions on a hyperbolic network

We analyze the phase transitions that emerge from the recursive design of certain hyperbolic networks that includes, for instance, a discontinuous ("explosive") transition in ordinary percolation. To this end, we solve the $q$-state Potts model in the analytic continuation for non-integer $q$ with the real-space renormalization group. We find exact expressions for this one-parameter family of models that describe the dramatic transformation of the transition. In particular, this variation in $q$ shows that the discontinuous transition is generic in the regime $q<2$ that includes percolation. A continuous ferromagnetic transition is recovered in a singular manner only for the Ising model, $q=2$. For $q>2$ the transition immediately transforms into an infinitely smooth order parameter of the Berezinskii-Kosterlitz-Thouless (BKT) type.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

One-Dimensional Coinless Quantum Walks

A coinless, discrete-time quantum walk possesses a Hilbert space whose dimension is smaller compared to the widely-studied coined walk. Coined walks require the direct product of the site basis with the coin space, coinless walks operate purely in the site basis, which is clearly minimal. These coinless quantum walks have received considerable attention recently because they have evolution operators that can be obtained by a graphical method based on lattice tessellations and they have been shown to be as efficient as the best known coined walks when used as a quantum search algorithm. We argue that both formulations in their most general form are equivalent. In particular, we demonstrate how to transform the one-dimensional version of the coinless quantum walk into an equivalent extended coined version for a specific family of evolution operators. We present some of its basic, asymptotic features for the one-dimensional lattice with some examples of tessellations, and analyze the mixing time and limiting probability distributions on cycles.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Renormalization Group Solution of the Chutes&Ladder Model

We analyze a semi-infinite one-dimensional random walk process with a biased motion that is incremental in one direction and long-range in the other. On a network with a fixed hierarchy of long-range jumps, we find with exact renormalization group calculations that there is a dynamical transition between a localized adsorption phase and an anomalous diffusion phase in which the mean-square displacement exponent depends non-universally on the Bernoulli coin. We relate these results to similar findings of unconventional phase behavior in hierarchical networks.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Scaling of Clusters near Discontinuous Percolation Transitions in Hyperbolic Networks

We investigate the onset of the discontinuous percolation transition in small-world hyperbolic networks by studying the systems-size scaling of the typical largest cluster approaching the transition, $p\nearrow p_{c}$. To this end, we determine the average size of the largest cluster $\left\langle s_{\rm max}\right\rangle \sim N^{Ψ\left(p\right)}$ in the thermodynamic limit using real-space renormalization of cluster generating functions for bond and site percolation in several models of hyperbolic networks that provide exact results. We determine that all our models conform to the recently predicted behavior regarding the growth of the largest cluster, which found diverging, albeit sub-extensive, clusters spanning the system with finite probability well below $p_{c}$ and at most quadratic corrections to unity in $Ψ\left(p\right)$ for $p\nearrow p_{c}$. Our study suggest a large universality in the cluster formation on small-world hyperbolic networks and the potential for an alternative mechanism in the cluster formation dynamics at the onset of discontinuous percolation transitions.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Weak Limit of the 3-State Quantum Walk on the Line

We revisit the one dimensional discrete time quantum walk with 3 states and the Grover coin. We derive analytic expressions for observed the localization, an long time approximation for the probability density function (PDF). We also connect the time averaged approximation to the PDF found by Inui et. al. to a spatial average of the walk. We show that this smooth approximation constitutes a proper PDF that predicts moments of the real PDF accurately.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Accumulation of beneficial mutations in one dimension

When beneficial mutations are relatively common, competition between multiple unfixed mutations can reduce the rate of fixation in well-mixed asexual populations. We introduce a one dimensional model with a steady accumulation of beneficial mutations. We find a transition between periodic selection and multiple-mutation regimes. In the multiple-mutation regime, the increase of fitness along the lattice bears a striking similarity to surface growth phenomena, with power law growth and saturation of the interface width. We also find significant differences compared to the well-mixed model. In our lattice model, the transition between regimes happens at a much lower mutation rate due to slower fixation times in one dimension. Also the rate of fixation is reduced with increasing mutation rate due to the more intense competition, and it saturates with large population size.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Finite-Size Corrections for Ground States of Edwards-Anderson Spin Glasses

Extensive computations of ground state energies of the Edwards-Anderson spin glass on bond-diluted, hypercubic lattices are conducted in dimensions d=3,..,7. Results are presented for bond-densities exactly at the percolation threshold, p=p_c, and deep within the glassy regime, p>p_c, where finding ground-states becomes a hard combinatorial problem. Finite-size corrections of the form 1/N^w are shown to be consistent throughout with the prediction w=1-y/d, where y refers to the "stiffness" exponent that controls the formation of domain wall excitations at low temperatures. At p=p_c, an extrapolation for $d\to\infty$ appears to match our mean-field results for these corrections. In the glassy phase, w does not approach the value of 2/3 for large d predicted from simulations of the Sherrington-Kirkpatrick spin glass. However, the value of w reached at the upper critical dimension does match certain mean-field spin glass models on sparse random networks of regular degree called Bethe lattices.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Optimization of transport protocols with path-length constraints in complex networks

We propose a protocol optimization technique that is applicable to both weighted or unweighted graphs. Our aim is to explore by how much a small variation around the Shortest Path or Optimal Path protocols can enhance protocol performance. Such an optimization strategy can be necessary because even though some protocols can achieve very high traffic tolerance levels, this is commonly done by enlarging the path-lengths, which may jeopardize scalability. We use ideas borrowed from Extremal Optimization to guide our algorithm, which proves to be an effective technique. Our method exploits the degeneracy of the paths or their close-weight alternatives, which significantly improves the scalability of the protocols in comparison to Shortest Paths or Optimal Paths protocols, keeping at the same time almost intact the length or weight of the paths. This characteristic ensures that the optimized routing protocols are composed of paths that are quick to traverse, avoiding negative effects in data communication due to path-length increases that can become specially relevant when information losses are present.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Simulations of Ground State Fluctuations in Mean-Field Ising Spin Glasses

The scaling of fluctuations in the distribution of ground-state energies or costs with the system size N for Ising spin glasses is considered using an extensive set of simulations with the Extremal Optimization heuristic across a range of different models on sparse and dense graphs. These models exhibit very diverse behaviors, and an asymptotic extrapolation is often complicated by higher-order corrections. The clearest picture, in fact, emerges from the study of graph-bipartitioning, a combinatorial optimization problem closely related to spin glasses. Aside from two-spin interactions with discrete bonds, we also consider problems with Gaussian bonds and three-spin interactions, which behave differently to a significant degree.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Conjecture on the maximum cut and bisection width in random regular graphs

Asymptotic properties of random regular graphs are object of extensive study in mathematics. In this note we argue, based on theory of spin glasses, that in random regular graphs the maximum cut size asymptotically equals the number of edges in the graph minus the minimum bisection size. Maximum cut and minimal bisection are two famous NP-complete problems with no known general relation between them, hence our conjecture is a surprising property of random regular graphs. We further support the conjecture with numerical simulations. A rigorous proof of this relation is obviously a challenge.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

The Peculiar Phase Structure of Random Graph Bisection

The mincut graph bisection problem involves partitioning the n vertices of a graph into disjoint subsets, each containing exactly n/2 vertices, while minimizing the number of "cut" edges with an endpoint in each subset. When considered over sparse random graphs, the phase structure of the graph bisection problem displays certain familiar properties, but also some surprises. It is known that when the mean degree is below the critical value of 2 log 2, the cutsize is zero with high probability. We study how the minimum cutsize increases with mean degree above this critical threshold, finding a new analytical upper bound that improves considerably upon previous bounds. Combined with recent results on expander graphs, our bound suggests the unusual scenario that random graph bisection is replica symmetric up to and beyond the critical threshold, with a replica symmetry breaking transition possibly taking place above the threshold. An intriguing algorithmic consequence is that although the problem is NP-hard, we can find near-optimal cutsizes (whose ratio to the optimal value approaches 1 asymptotically) in polynomial time for typical instances near the phase transition.

0 citations0 reviewsNo code linkedOpen access
preprint2005arXiv

Extremal Optimization for Sherrington-Kirkpatrick Spin Glasses

Extremal Optimization (EO), a new local search heuristic, is used to approximate ground states of the mean-field spin glass model introduced by Sherrington and Kirkpatrick. The implementation extends the applicability of EO to systems with highly connected variables. Approximate ground states of sufficient accuracy and with statistical significance are obtained for systems with more than N=1000 variables using $\pm J$ bonds. The data reproduces the well-known Parisi solution for the average ground state energy of the model to about 0.01%, providing a high degree of confidence in the heuristic. The results support to less than 1% accuracy rational values of $ω=2/3$ for the finite-size correction exponent, and of $ρ=3/4$ for the fluctuation exponent of the ground state energies, neither one of which has been obtained analytically yet. The probability density function for ground state energies is highly skewed and identical within numerical error to the one found for Gaussian bonds. But comparison with infinite-range models of finite connectivity shows that the skewness is connectivity-dependent.

0 citations0 reviewsNo code linkedOpen access
preprint2005arXiv

Stiffness of the Edwards-Anderson Model in all Dimensions

A comprehensive description in all dimensions is provided for the scaling exponent $y$ of low-energy excitations in the Ising spin glass introduced by Edwards and Anderson. A combination of extensive numerical as well as theoretical results suggest that its lower critical dimension is {\it exactly} $d_l=5/2$. Such a result would be an essential feature of any complete model of low-temperature spin glass order and imposes a constraint that may help to distinguish between theories.

0 citations0 reviewsNo code linkedOpen access
preprint2000arXiv

Double-Scaling Limit of a Broken Symmetry Quantum Field Theory

The Ising limit of a conventional Hermitian parity-symmetric scalar quantum field theory is a correlated limit in which two bare Lagrangian parameters, the coupling constant $g$ and the {\it negative} mass squared $-m^2$, both approach infinity with the ratio $-m^2/g=α>0$ held fixed. In this limit the renormalized mass of the asymptotic theory is finite. Moreover, the limiting theory exhibits universal properties. For a non-Hermitian $\cal PT$-symmetric Lagrangian lacking parity symmetry, whose interaction term has the form $-g(iϕ)^N/N$, the renormalized mass diverges in this correlated limit. Nevertheless, the asymptotic theory still has interesting properties. For example, the one-point Green's function approaches the value $-iα^{1/(N-2)}$ independently of the space-time dimension $D$ for $D<2$. Moreover, while the Ising limit of a parity-symmetric quantum field theory is dominated by a dilute instanton gas, the corresponding correlated limit of a $\cal PT$-symmetric quantum field theory without parity symmetry is dominated by a constant-field configuration with corrections determined by a weak-coupling expansion in which the expansion parameter (the amplitude of the vertices of the graphs in this expansion) is proportional to an inverse power of $g$. We thus observe a weak-coupling/strong-coupling duality in that while the Ising limit is a strong-coupling limit of the quantum field theory, the expansion about this limit takes the form of a conventional weak-coupling expansion. A possible generalization of the Ising limit to dimensions $D<4$ is briefly discussed.

0 citations0 reviewsNo code linkedOpen access
preprint1995arXiv

SPHERICALLY SYMMETRIC RANDOM WALKS II. DIMENSIONALLY DEPENDENT CRITICAL BEHAVIOR

A recently developed model of random walks on a $D$-dimensional hyperspherical lattice, where $D$ is {\sl not} restricted to integer values, is extended to include the possibility of creating and annihilating random walkers. Steady-state distributions of random walkers are obtained for all dimensions $D>0$ by solving a discrete eigenvalue problem. These distributions exhibit dimensionally dependent critical behavior as a function of the birth rate. This remarkably simple model exhibits a second-order phase transition with a nontrivial critical exponent for all dimensions $D>0$.

0 citations0 reviewsNo code linkedOpen access
preprint1995arXiv

SPHERICALLY SYMMETRIC RANDOM WALKS III. POLYMER ADSORPTION AT A HYPERSPHERICAL BOUNDARY

A recently developed model of random walks on a $D$-dimensional hyperspherical lattice, where $D$ is {\sl not} restricted to integer values, is used to study polymer growth near a $D$-dimensional attractive hyperspherical boundary. The model determines the fraction $P(κ)$ of the polymer adsorbed on this boundary as a function of the attractive potential $κ$ for all values of $D$. The adsorption fraction $P(κ)$ exhibits a second-order phase transition with a nontrivial scaling coefficient for $0<D<4$, $D\neq 2$, and exhibits a first-order phase transition for $D>4$. At $D=4$ there is a tricritical point with logarithmic scaling. This model reproduces earlier results for $D=1$ and $D=2$, where $P(κ)$ scales linearly and exponentially, respectively. A crossover transition that depends on the radius of the adsorbing boundary is found.

0 citations0 reviewsNo code linkedOpen access