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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We establish the average-case hardness of the algorithmic problem of exactcomputation of the partition function associated with theSherrington-Kirkpatrick model of spin glasses with Gaussian couplings andrandom external field. In particular, we establish that unless $P= \#P$, theredoes not exist a polynomial-time algorithm to exactly compute the partitionfunction on average. This is done by showing that if there exists a polynomialtime algorithm, which exactly computes the partition function for inversepolynomial fraction ($1/n^{O(1)}$) of all inputs, then there is a polynomialtime algorithm, which exactly computes the partition function for all inputs,with high probability, yielding $P=\#P$. The computational model that we adoptis {\em finite-precision arithmetic}, where the algorithmic inputs aretruncated first to a certain level $N$ of digital precision. The ingredients ofour proof include the random and downward self-reducibility of the partitionfunction with random external field; an argument of Cai et al.\cite{cai1999hardness} for establishing the average-case hardness of computingthe permanent of a matrix; a list-decoding algorithm of Sudan\cite{sudan1996maximum}, for reconstructing polynomials intersecting a givenlist of numbers at sufficiently many points; and near-uniformity of thelog-normal distribution, modulo a large prime $p$. To the best of ourknowledge, our result is the first one establishing a provable hardness of amodel arising in the field of spin glasses.  Furthermore, we extend our result to the same problem under a different {\emreal-valued} computational model, e.g. using a Blum-Shub-Smale machine\cite{blum1988theory} operating over real-valued inputs.

Computing the partition function of the Sherrington-Kirkpatrick model is hard on average