English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Random constraint satisfaction problems can display a very rich structure inthe space of solutions, with often an ergodicity breaking -- also known asclustering or dynamical -- transition preceding the satisfiability thresholdwhen the constraint-to-variables ratio $\alpha$ is increased. However, smartalgorithms start to fail finding solutions in polynomial time at some threshold$\alpha_{\rm alg}$ which is algorithmic dependent and generally bigger than thedynamical one $\alpha_d$. The reason for this discrepancy is due to the factthat $\alpha_d$ is traditionally computed according to the uniform measure overall the solutions. Thus, while bounding the region where a uniform sampling ofthe solutions is easy, it cannot predict the performance of off-equilibriumprocesses, that are still able of finding atypical solutions even beyond$\alpha_d$. Here we show that a reconciliation between algorithmic behaviourand thermodynamic prediction is nonetheless possible at least up to somethreshold $\alpha_d^{\rm opt}\geq\alpha_d$, which is defined as the maximumvalue of the dynamical threshold computed on all possible probability measuresover the solutions. We consider a simple Monte Carlo-based optimizationalgorithm, which is restricted to the solution space, and we demonstrate thatsampling the equilibrium distribution of a biased measure improving on$\alpha_d$ is still possible even beyond the ergodicity breaking point for theuniform measure, where other algorithms hopelessly enter the out-of-equilibriumregime. The conjecture we put forward is that many smart algorithms sample thesolution space according to a biased measure: once this measure is identified,the algorithmic threshold is given by the corresponding ergodicity-breakingtransition.

Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold