1
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: not found
      • Article: not found

      Inferring the origin of an epidemic with a dynamic message-passing algorithm

      Read this article at

      ScienceOpenPublisherPubMed
      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Related collections

          Most cited references15

          • Record: found
          • Abstract: not found
          • Article: not found

          Low-density parity-check codes

            Bookmark
            • Record: found
            • Abstract: not found
            • Book: not found

            Information, Physics, and Computation

              Bookmark
              • Record: found
              • Abstract: found
              • Article: not found

              Analytic and algorithmic solution of random satisfiability problems.

              We study the satisfiability of random Boolean expressions built from many clauses with K variables per clause (K-satisfiability). Expressions with a ratio alpha of clauses to variables less than a threshold alphac are almost always satisfiable, whereas those with a ratio above this threshold are almost always unsatisfiable. We show the existence of an intermediate phase below alphac, where the proliferation of metastable states is responsible for the onset of complexity in search algorithms. We introduce a class of optimization algorithms that can deal with these metastable states; one such algorithm has been tested successfully on the largest existing benchmark of K-satisfiability.
                Bookmark

                Author and article information

                Journal
                PLEEE8
                Physical Review E
                Phys. Rev. E
                American Physical Society (APS)
                1539-3755
                1550-2376
                July 2014
                July 1 2014
                : 90
                : 1
                Article
                10.1103/PhysRevE.90.012801
                25122336
                31cba0f1-63ce-4909-8ffd-cdc7f17ea6d4
                © 2014

                http://link.aps.org/licenses/aps-default-license

                History

                Comments

                Comment on this article