Replication-based inference algorithms for hard computational problems

Roberto C. Alamino; Juan P. Neirotti; David Saad

doi:10.1103/PhysRevE.88.013313

Replication-based inference algorithms for hard computational problems

Roberto C. Alamino^*, Juan P. Neirotti, David Saad

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

Abstract

Inference algorithms based on evolving interactions between replicated solutions are introduced and analyzed on a prototypical NP-hard problem: the capacity of the binary Ising perceptron. The efficiency of the algorithm is examined numerically against that of the parallel tempering algorithm, showing improved performance in terms of the results obtained, computing requirements and simplicity of implementation. © 2013 American Physical Society.

Original language	English
Article number	013313
Number of pages	10
Journal	Physical Review E
Volume	88
Issue number	1
DOIs	https://doi.org/10.1103/PhysRevE.88.013313
Publication status	Published - 31 Jul 2013

Bibliographical note

Access to Document

10.1103/PhysRevE.88.013313

Replication-based inference algorithms for hard computational problems
© 2013 American Physical Society
Final published version, 184 KB

http://journals.aps.org/pre/abstract/10.1103/PhysRevE.88.013313

Cite this

@article{4c12125177b44a7099d90a70a81d425e,

title = "Replication-based inference algorithms for hard computational problems",

abstract = "Inference algorithms based on evolving interactions between replicated solutions are introduced and analyzed on a prototypical NP-hard problem: the capacity of the binary Ising perceptron. The efficiency of the algorithm is examined numerically against that of the parallel tempering algorithm, showing improved performance in terms of the results obtained, computing requirements and simplicity of implementation. {\textcopyright} 2013 American Physical Society.",

author = "{C. Alamino}, Roberto and {P. Neirotti}, Juan and David Saad",

note = "{\textcopyright} 2013 American Physical Society",

year = "2013",

month = jul,

day = "31",

doi = "10.1103/PhysRevE.88.013313",

language = "English",

volume = "88",

journal = "Physical Review E",

issn = "1539-3755",

publisher = "American Physical Society",

number = "1",

}

TY - JOUR

T1 - Replication-based inference algorithms for hard computational problems

AU - C. Alamino, Roberto

AU - P. Neirotti, Juan

AU - Saad, David

PY - 2013/7/31

Y1 - 2013/7/31

N2 - Inference algorithms based on evolving interactions between replicated solutions are introduced and analyzed on a prototypical NP-hard problem: the capacity of the binary Ising perceptron. The efficiency of the algorithm is examined numerically against that of the parallel tempering algorithm, showing improved performance in terms of the results obtained, computing requirements and simplicity of implementation. © 2013 American Physical Society.

AB - Inference algorithms based on evolving interactions between replicated solutions are introduced and analyzed on a prototypical NP-hard problem: the capacity of the binary Ising perceptron. The efficiency of the algorithm is examined numerically against that of the parallel tempering algorithm, showing improved performance in terms of the results obtained, computing requirements and simplicity of implementation. © 2013 American Physical Society.

UR - http://www.scopus.com/inward/record.url?scp=84882349354&partnerID=8YFLogxK

U2 - 10.1103/PhysRevE.88.013313

DO - 10.1103/PhysRevE.88.013313

M3 - Article

C2 - 23944589

SN - 1539-3755

VL - 88

JO - Physical Review E

JF - Physical Review E

IS - 1

M1 - 013313

ER -

Replication-based inference algorithms for hard computational problems

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this