{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:05:54Z","timestamp":1750694754442,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":49,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ONR","award":["N00014-17-1-2147"],"award-info":[{"award-number":["N00014-17-1-2147"]}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1453261,CCF-1565235"],"award-info":[{"award-number":["CCF-1453261,CCF-1565235"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316372","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"828-839","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Learning restricted Boltzmann machines via influence maximization"],"prefix":"10.1145","author":[{"given":"Guy","family":"Bresler","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frederic","family":"Koehler","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ankur","family":"Moitra","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Animashree Anandkumar Vincent YF Tan Furong Huang and Alan S Willsky. 2012. High-dimensional structure estimation in Ising models: Local separation criterion. The Annals of Statistics (2012) 1346\u20131375.  Animashree Anandkumar Vincent YF Tan Furong Huang and Alan S Willsky. 2012. High-dimensional structure estimation in Ising models: Local separation criterion. The Annals of Statistics (2012) 1346\u20131375."},{"key":"e_1_3_2_1_2_1","unstructured":"Animashree Anandkumar and Ragupathyraj Valluvan. 2013.  Animashree Anandkumar and Ragupathyraj Valluvan. 2013."},{"key":"e_1_3_2_1_3_1","unstructured":"Learning loopy graphical models with latent variables: Efficient methods and guarantees. The Annals of Statistics (2013) 401\u2013435.  Learning loopy graphical models with latent variables: Efficient methods and guarantees. The Annals of Statistics (2013) 401\u2013435."},{"volume-title":"International Conference on Machine Learning. 584\u2013592","year":"2014","author":"Arora Sanjeev","key":"e_1_3_2_1_4_1"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-014-9243-7"},{"key":"e_1_3_2_1_6_1","unstructured":"Andrej Bogdanov Elchanan Mossel and Salil Vadhan. 2008.  Andrej Bogdanov Elchanan Mossel and Salil Vadhan. 2008."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85363-3_27"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746631"},{"key":"e_1_3_2_1_9_1","unstructured":"Guy Bresler David Gamarnik and Devavrat Shah. 2014. Hardness of parameter estimation in graphical models. In Advances in Neural Information Processing Systems. 1062\u20131070.   Guy Bresler David Gamarnik and Devavrat Shah. 2014. Hardness of parameter estimation in graphical models. In Advances in Neural Information Processing Systems. 1062\u20131070."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85363-3_28"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72792-7_15"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1214\/11-AOS949"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1968.1054142"},{"volume-title":"Proceedings of the fourteenth international conference on artificial intelligence and statistics. 215\u2013223","year":"2011","author":"Coates Adam","key":"e_1_3_2_1_14_1"},{"volume-title":"Conference on Learning Theory. 907\u2013940","year":"2016","author":"Eldan Ronen","key":"e_1_3_2_1_15_1"},{"key":"e_1_3_2_1_16_1","unstructured":"Surbhi Goel and Adam Klivans. 2017. Learning depth-three neural networks in polynomial time. arXiv preprint arXiv:1709.06010 (2017).  Surbhi Goel and Adam Klivans. 2017. Learning depth-three neural networks in polynomial time. arXiv preprint arXiv:1709.06010 (2017)."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1665211"},{"key":"e_1_3_2_1_18_1","unstructured":"Linus Hamilton Frederic Koehler and Ankur Moitra. 2017. Information theoretic properties of Markov random fields and their algorithmic applications. In Advances in Neural Information Processing Systems. 2460\u20132469.   Linus Hamilton Frederic Koehler and Ankur Moitra. 2017. Information theoretic properties of Markov random fields and their algorithmic applications. In Advances in Neural Information Processing Systems. 2460\u20132469."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.4249\/scholarpedia.5947"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Geoffrey E Hinton and Ruslan R Salakhutdinov. 2006. Reducing the dimensionality of data with neural networks. science 313 5786 (2006) 504\u2013507.  Geoffrey E Hinton and Ruslan R Salakhutdinov. 2006. Reducing the dimensionality of data with neural networks. science 313 5786 (2006) 504\u2013507.","DOI":"10.1126\/science.1127647"},{"key":"e_1_3_2_1_21_1","unstructured":"Geoffrey E Hinton and Ruslan R Salakhutdinov. 2009. Replicated softmax: an undirected topic model. In Advances in neural information processing systems. 1607\u20131614.   Geoffrey E Hinton and Ruslan R Salakhutdinov. 2009. Replicated softmax: an undirected topic model. In Advances in neural information processing systems. 1607\u20131614."},{"key":"e_1_3_2_1_22_1","unstructured":"Majid Janzamin Hanie Sedghi and Anima Anandkumar. 2015. Beating the perils of non-convexity: Guaranteed training of neural networks using tensor methods. arXiv preprint arXiv:1506.08473 (2015).  Majid Janzamin Hanie Sedghi and Anima Anandkumar. 2015. Beating the perils of non-convexity: Guaranteed training of neural networks using tensor methods. arXiv preprint arXiv:1506.08473 (2015)."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"M. Jerrum and A. Sinclair. 1990. Polynomial-Time Approximation Algorithms for Ising Model (Extended Abstract). In Automata Languages and Programming. 462\u2013475.   M. Jerrum and A. Sinclair. 1990. Polynomial-Time Approximation Algorithms for Ising Model (Extended Abstract). In Automata Languages and Programming. 462\u2013475.","DOI":"10.1007\/BFb0032051"},{"key":"e_1_3_2_1_24_1","unstructured":"Sham M Kakade Varun Kanade Ohad Shamir and Adam Kalai. 2011. Efficient learning of generalized linear and single index models with isotonic regression. In Advances in Neural Information Processing Systems. 927\u2013935.   Sham M Kakade Varun Kanade Ohad Shamir and Adam Kalai. 2011. Efficient learning of generalized linear and single index models with isotonic regression. In Advances in Neural Information Processing Systems. 927\u2013935."},{"volume-title":"Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 392\u2013401","year":"2001","author":"Karger David","key":"e_1_3_2_1_25_1"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Adam Klivans and Raghu Meka. 2017. Learning Graphical Models Using Multiplicative Weights. In FOCS.  Adam Klivans and Raghu Meka. 2017. Learning Graphical Models Using Multiplicative Weights. In FOCS.","DOI":"10.1109\/FOCS.2017.39"},{"key":"e_1_3_2_1_27_1","unstructured":"Tsung-Dao Lee and Chen-Ning Yang. 1952.  Tsung-Dao Lee and Chen-Ning Yang. 1952."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Statistical theory of equations of state and phase transitions. II. Lattice gas and Ising model. Physical Review 87 3 (1952) 410.  Statistical theory of equations of state and phase transitions. II. Lattice gas and Ising model. Physical Review 87 3 (1952) 410.","DOI":"10.1103\/PhysRev.87.410"},{"key":"e_1_3_2_1_29_1","unstructured":"Jingcheng Liu Alistair Sinclair and Piyush Srivastava. 2017.  Jingcheng Liu Alistair Sinclair and Piyush Srivastava. 2017."},{"volume-title":"Ising Partition Function: Zeros and Deterministic Approximation. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)","year":"2017","author":"The","key":"e_1_3_2_1_30_1"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/3104322.3104412"},{"key":"e_1_3_2_1_32_1","unstructured":"Christopher W Lynn and Daniel D Lee. 2018.  Christopher W Lynn and Daniel D Lee. 2018."},{"key":"e_1_3_2_1_33_1","unstructured":"Maximizing Activity in Ising Networks via the TAP Approximation. arXiv preprint arXiv:1803.00110 (2018).  Maximizing Activity in Ising Networks via the TAP Approximation. arXiv preprint arXiv:1803.00110 (2018)."},{"key":"e_1_3_2_1_34_1","unstructured":"James Martens Arkadev Chattopadhya Toni Pitassi and Richard Zemel. 2013.  James Martens Arkadev Chattopadhya Toni Pitassi and Richard Zemel. 2013."},{"key":"e_1_3_2_1_35_1","unstructured":"On the representational efficiency of restricted boltzmann machines. In Advances in Neural Information Processing Systems. 2877\u20132885.   On the representational efficiency of restricted boltzmann machines. In Advances in Neural Information Processing Systems. 2877\u20132885."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780574"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_3_2_1_38_1","unstructured":"Pradeep Ravikumar Martin J Wainwright John D Lafferty etal 2010.  Pradeep Ravikumar Martin J Wainwright John D Lafferty et al. 2010."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Highdimensional Ising model selection using ?1-regularized logistic regression. The Annals of Statistics 38 3 (2010) 1287\u20131319.  Highdimensional Ising model selection using ?1-regularized logistic regression. The Annals of Statistics 38 3 (2010) 1287\u20131319.","DOI":"10.1214\/09-AOS691"},{"key":"e_1_3_2_1_40_1","unstructured":"Itay Safran and Ohad Shamir. 2017.  Itay Safran and Ohad Shamir. 2017."},{"volume-title":"International Conference on Machine Learning. 2979\u20132987","key":"e_1_3_2_1_41_1"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273496.1273596"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2191659"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.56"},{"volume-title":"Conference on Learning Theory. 1517\u20131539","year":"2016","author":"Telgarsky Matus","key":"e_1_3_2_1_45_1"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.27"},{"key":"e_1_3_2_1_47_1","unstructured":"Marc Vuffray Sidhant Misra Andrey Lokhov and Michael Chertkov. 2016. Interaction screening: Efficient and sample-optimal learning of Ising models. In Advances in Neural Information Processing Systems. 2595\u20132603.   Marc Vuffray Sidhant Misra Andrey Lokhov and Michael Chertkov. 2016. Interaction screening: Efficient and sample-optimal learning of Ising models. In Advances in Neural Information Processing Systems. 2595\u20132603."},{"key":"e_1_3_2_1_48_1","unstructured":"Yuchen Zhang Jason D Lee and Michael I Jordan. 2016.  Yuchen Zhang Jason D Lee and Michael I Jordan. 2016."},{"volume-title":"International Conference on Machine Learning. 993\u20131001","key":"e_1_3_2_1_49_1"}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Phoenix AZ USA","acronym":"STOC '19"},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316372","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316372","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316372","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:32Z","timestamp":1750204472000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316372"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":49,"alternative-id":["10.1145\/3313276.3316372","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316372","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}