{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:31:43Z","timestamp":1725517903200},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540853626"},{"type":"electronic","value":"9783540853633"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85363-3_27","type":"book-chapter","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T19:29:28Z","timestamp":1219865368000},"page":"331-342","source":"Crossref","is-referenced-by-count":16,"title":["The Complexity of Distinguishing Markov Random Fields"],"prefix":"10.1007","author":[{"given":"Andrej","family":"Bogdanov","sequence":"first","affiliation":[]},{"given":"Elchanan","family":"Mossel","sequence":"additional","affiliation":[]},{"given":"Salil","family":"Vadhan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"27_CR1","doi-asserted-by":"crossref","unstructured":"Friedman, N.: Infering cellular networks using probalistic graphical models. Science (2004)","DOI":"10.1126\/science.1094068"},{"key":"27_CR2","unstructured":"Kasif, S.: Bayes networks and graphical models in computational molecular biology and bioinformatics, survey of recent research (2007), http:\/\/genomics10.bu.edu\/bioinformatics\/kasif\/bayes-net.html"},{"key":"27_CR3","volume-title":"Inferring Phylogenies","author":"J. Felsenstein","year":"2004","unstructured":"Felsenstein, J.: Inferring Phylogenies. Sinauer, New York (2004)"},{"key":"27_CR4","series-title":"Mathematics and its Applications series","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198509424.001.0001","volume-title":"Phylogenetics","author":"C. Semple","year":"2003","unstructured":"Semple, C., Steel, M.: Phylogenetics. Mathematics and its Applications series, vol.\u00a022. Oxford University Press, Oxford (2003)"},{"issue":"2","key":"27_CR5","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1002\/(SICI)1098-2418(199903)14:2<153::AID-RSA3>3.0.CO;2-R","volume":"14","author":"P.L. Erd\u00f6s","year":"1999","unstructured":"Erd\u00f6s, P.L., Steel, M.A., Sz\u00e9kely, L.A., Warnow, T.A.: A few logs suffice to build (almost) all trees (part 1). Random Structures Algorithms\u00a014(2), 153\u2013184 (1999)","journal-title":"Random Structures Algorithms"},{"key":"27_CR6","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1109\/TCBB.2007.1010","volume":"4","author":"E. Mossel","year":"2007","unstructured":"Mossel, E.: Distorted metrics on trees and phylogenetic forests. IEEE Computational Biology and Bioinformatics\u00a04, 108\u2013116 (2007)","journal-title":"IEEE Computational Biology and Bioinformatics"},{"key":"27_CR7","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Mossel, E., Roch, S.: Optimal phylogenetic reconstruction. In: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing (STOC 2006), pp. 159\u2013168 (2006)","DOI":"10.1145\/1132516.1132540"},{"key":"27_CR8","first-page":"1743","volume":"7","author":"P. Abbeel","year":"2006","unstructured":"Abbeel, P., Koller, D., Ng, A.Y.: Learning factor graphs in polynomial time and sampling complexity. Journal of Machine Learning Research\u00a07, 1743\u20131788 (2006)","journal-title":"Journal of Machine Learning Research"},{"key":"27_CR9","unstructured":"Bresler, G., Mossel, E., Sly, A.: Reconstruction of Markov random fields from samples: Some easy observations and algorithms. These proceedings (2008), http:\/\/front.math.ucdavis.edu\/0712.1402"},{"key":"27_CR10","doi-asserted-by":"crossref","unstructured":"Wainwright, M.J., Ravikumar, P., Lafferty, J.D.: High dimensional graphical model selection using \u21131-regularized logistic regression. In: Proceedings of the NIPS (2006)","DOI":"10.7551\/mitpress\/7503.003.0188"},{"key":"27_CR11","volume-title":"Progress in Theoretical Computer Science","author":"A. Sinclair","year":"1993","unstructured":"Sinclair, A.: Algorithms for Random Generation and Counting: A Markov chain Approach. In: Progress in Theoretical Computer Science. Birkh\u00e4user, Basel (1993)"},{"issue":"3\u20134","key":"27_CR12","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<229::AID-RSA3>3.0.CO;2-X","volume":"15","author":"M. Luby","year":"1999","unstructured":"Luby, M., Vigoda, E.: Fast convergence of the Glauber dynamics for sampling independent sets. Random Struct. Algorithms\u00a015(3\u20134), 229\u2013241 (1999)","journal-title":"Random Struct. Algorithms"},{"key":"27_CR13","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"M. Jerrum","year":"1986","unstructured":"Jerrum, M., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. Theor. Comput. Sci.\u00a043, 169\u2013188 (1986)","journal-title":"Theor. Comput. Sci."},{"key":"27_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/11685654_12","volume-title":"Theoretical Computer Science","author":"O. Goldreich","year":"2006","unstructured":"Goldreich, O.: On promise problems: a survey. In: Goldreich, O., Rosenberg, A.L., Selman, A.L. (eds.) Theoretical Computer Science. LNCS, vol.\u00a03895, pp. 254\u2013290. Springer, Heidelberg (2006)"},{"key":"27_CR15","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0019-9958(84)80056-X","volume":"61","author":"S. Even","year":"1984","unstructured":"Even, S., Selman, A.L., Yacobi, Y.: The complexity of promise problems with applications to public-key cryptography. Information and Control\u00a061, 159\u2013173 (1984)","journal-title":"Information and Control"},{"key":"27_CR16","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546891","volume-title":"Foundations of cryptography (Basic tools)","author":"O. Goldreich","year":"2001","unstructured":"Goldreich, O.: Foundations of cryptography (Basic tools). Cambridge University Press, Cambridge (2001)"},{"issue":"4","key":"27_CR17","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM Journal on Computing\u00a028(4), 1364\u20131396 (1999)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"27_CR18","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1145\/116825.116852","volume":"38","author":"O. Goldreich","year":"1991","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity, or All languages in NP have zero-knowledge proof systems. Journal of the Association for Computing Machinery\u00a038(3), 691\u2013729 (1991)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"27_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1007\/3-540-48184-2_4","volume-title":"Advances in Cryptology - CRYPTO \u201987","author":"R. Impagliazzo","year":"1988","unstructured":"Impagliazzo, R., Yung, M.: Direct minimum-knowledge computations (extended abstract). In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol.\u00a0293, pp. 40\u201351. Springer, Heidelberg (1988)"},{"key":"27_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/0-387-34799-2_4","volume-title":"Advances in Cryptology - CRYPTO \u201988","author":"M. Ben-Or","year":"1990","unstructured":"Ben-Or, M., Goldreich, O., Goldwasser, S., H\u00e5stad, J., Kilian, J., Micali, S., Rogaway, P.: Everything provable is provable in zero-knowledge. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol.\u00a0403, pp. 37\u201356. Springer, Heidelberg (1990)"},{"key":"27_CR21","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1109\/ISTCS.1993.253489","volume-title":"Proc. 2nd Israel Symp. on Theory of Computing and Systems","author":"R. Ostrovsky","year":"1993","unstructured":"Ostrovsky, R., Wigderson, A.: One-way functions are essential for non-trivial zero knowledge. In: Proc. 2nd Israel Symp. on Theory of Computing and Systems, pp. 3\u201317. IEEE Computer Society Press, Los Alamitos (1993)"},{"issue":"2","key":"27_CR22","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1145\/636865.636868","volume":"50","author":"A. Sahai","year":"2003","unstructured":"Sahai, A., Vadhan, S.: A complete problem for statistical zero knowledge. Journal of the ACM\u00a050(2), 196\u2013249 (2003)","journal-title":"Journal of the ACM"},{"key":"27_CR23","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","volume":"36","author":"L. Babai","year":"1988","unstructured":"Babai, L., Moran, S.: Arthur-Merlin games: A randomized proof system and a hierarchy of complexity classes. Journal of Computer and System Sciences\u00a036, 254\u2013276 (1988)","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85363-3_27.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,29]],"date-time":"2024-02-29T14:10:02Z","timestamp":1709215802000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85363-3_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540853626","9783540853633"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85363-3_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}