{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:09:07Z","timestamp":1750219747933,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":50,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council","award":["815464"],"award-info":[{"award-number":["815464"]}]},{"name":"Ministry of Education, Taiwan","award":["NTU-112V1023-2"],"award-info":[{"award-number":["NTU-112V1023-2"]}]},{"name":"MUR FARE2020 PAReCoDi","award":[""],"award-info":[{"award-number":[""]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649643","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"172-182","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Private Graphon Estimation via Sum-of-Squares"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-0016-3462","authenticated-orcid":false,"given":"Hongjie","family":"Chen","sequence":"first","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-2142-0501","authenticated-orcid":false,"given":"Jingqiu","family":"Ding","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-9808-6354","authenticated-orcid":false,"given":"Tommaso","family":"D'Orsi","sequence":"additional","affiliation":[{"name":"BIDSA, Bocconi University, Milan, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-7824-8965","authenticated-orcid":false,"given":"Yiding","family":"Hua","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9683-5982","authenticated-orcid":false,"given":"Chih-Hung","family":"Liu","sequence":"additional","affiliation":[{"name":"National Taiwan University, Taipei, Taiwan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3908-8180","authenticated-orcid":false,"given":"David","family":"Steurer","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Emmanuel Abbe. 2017. Community detection and stochastic block models. arXiv preprint arXiv:1703.10146.","DOI":"10.1561\/9781680834772"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519953"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055488"},{"key":"e_1_3_2_1_4_1","unstructured":"Boaz Barak and David Steurer. 2014. Sum-of-squares proofs and the quest toward optimal algorithms. arXiv preprint arXiv:1404.5236."},{"key":"e_1_3_2_1_5_1","unstructured":"Boaz Barak and David Steurer. 2016. Proofs beliefs and algorithms through the lens of sum-of-squares. lecture notes. https:\/\/www.sumofsquares.org"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.67"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422449"},{"key":"e_1_3_2_1_8_1","volume-title":"Revealing Network Structure","author":"Borgs Christian","year":"1810","unstructured":"Christian Borgs, Jennifer Chayes, Adam Smith, and Ilias Zadik. 2018. Revealing Network Structure, Confidentially: Improved Rates for Node-Private Graphon Estimation. arxiv:1810.02183."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1214\/20-aos1985"},{"key":"e_1_3_2_1_10_1","unstructured":"Christian Borgs Jennifer T. Chayes and Adam Smith. 2015. Private Graphon Estimation for Sparse Graphs. arxiv:1506.06162."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585184"},{"key":"e_1_3_2_1_12_1","unstructured":"Rares-Darius Buhai and David Steurer. 2023. Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures. arxiv:2112.05445."},{"key":"e_1_3_2_1_13_1","unstructured":"Hongjie Chen Vincent Cohen-Addad Tommaso d\u2019Orsi Alessandro Epasto Jacob Imola David Steurer and Stefan Tiegel. 2023. Private estimation algorithms for stochastic block models and mixture models. arXiv preprint arXiv:2301.04822."},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005","author":"Coja-Oghlan Amin","year":"2005","unstructured":"Amin Coja-Oghlan. 2005. A spectral heuristic for bisecting random graphs. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005. SIAM, 850\u2013859. http:\/\/dl.acm.org\/citation.cfm?id=1070432.1070552"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.07.022"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_3_2_1_17_1","volume-title":"The algorithmic foundations of differential privacy. Foundations and Trends\u00ae in Theoretical Computer Science, 9, 3\u20134","author":"Dwork Cynthia","year":"2014","unstructured":"Cynthia Dwork and Aaron Roth. 2014. The algorithmic foundations of differential privacy. Foundations and Trends\u00ae in Theoretical Computer Science, 9, 3\u20134 (2014), 211\u2013407."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1214\/15-AOS1354"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_19"},{"key":"e_1_3_2_1_20_1","unstructured":"Olivier Gu\u00e9don and Roman Vershynin. 2014. Community detection in sparse networks via Grothendieck\u2019s inequality. arxiv:1411.4686v4."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.11"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1214\/19-AOS1843"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519947"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Samuel B. Hopkins Gautam Kamath Mahbod Majid and Shyam Narayanan. 2022. Robustness Implies Privacy in Statistical Estimation. arxiv:2212.05015.","DOI":"10.1145\/3564246.3585115"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188748"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.42"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Iden Kalemaj Sofya Raskhodnikova Adam Smith and Charalampos E Tsourakakis. 2023. Node-Differentially Private Estimation of the Number of Connected Components. arXiv preprint arXiv:2304.05890.","DOI":"10.1145\/3584372.3588671"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611523"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_26"},{"volume-title":"Theory of Cryptography","author":"Kasiviswanathan Shiva Prasad","key":"e_1_3_2_1_30_1","unstructured":"Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. 2013. Analyzing Graphs with Node Differential Privacy. In Theory of Cryptography, Amit Sahai (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg. 457\u2013476. isbn:978-3-642-36594-2"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1214\/16-AOS1454"},{"key":"e_1_3_2_1_32_1","first-page":"316","article-title":"ORACLE INEQUALITIES FOR NETWORK MODELS AND SPARSE GRAPHON ESTIMATION","volume":"45","author":"OLGA KLOPP, ALEXANDRE","year":"2017","unstructured":"OLGA KLOPP, ALEXANDRE B TSYBAKOV, and NICOLAS VERZELEN. 2017. ORACLE INEQUALITIES FOR NETWORK MODELS AND SPARSE GRAPHON ESTIMATION. Annals of Statistics, 45, 1 (2017), 316\u2013354.","journal-title":"Annals of Statistics"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188970"},{"key":"e_1_3_2_1_34_1","unstructured":"Yuetian Luo and Chao Gao. 2023. Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials. arxiv:2308.15728."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iax010"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.66"},{"key":"e_1_3_2_1_37_1","volume-title":"International Conference on Machine Learning. 15858\u201315894","author":"Mohamed Mohamed S","year":"2022","unstructured":"Mohamed S Mohamed, Dung Nguyen, Anil Vullikanti, and Ravi Tandon. 2022. Differentially private community detection for stochastic block models. In International Conference on Machine Learning. 15858\u201315894."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","unstructured":"Jiawang Nie and Markus Schweighofer. 2007. On the complexity of Putinar\u2019s Positivstellensatz. 135-150 pages. https:\/\/doi.org\/10.1016\/J.JCO.2006.07.002 10.1016\/J.JCO.2006.07.002","DOI":"10.1016\/J.JCO.2006.07.002"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250803"},{"key":"e_1_3_2_1_40_1","unstructured":"Gabriel Peyr\u00e9 Marco Cuturi and Justin Solomon. 2016. Gromov-Wasserstein Averaging of Kernel and Distance Matrices. ICML\u201916. JMLR.org 2664\u20132672."},{"key":"e_1_3_2_1_41_1","volume-title":"Proceedings of the 2017 Conference on Learning Theory.","author":"Potechin Aaron","year":"2017","unstructured":"Aaron Potechin and David Steurer. 2017. Exact tensor completion with sum-of-squares. In Proceedings of the 2017 Conference on Learning Theory."},{"key":"e_1_3_2_1_42_1","volume-title":"Proceedings of the International Congress of Mathematicians: Rio de Janeiro","author":"Raghavendra Prasad","year":"2018","unstructured":"Prasad Raghavendra, Tselil Schramm, and David Steurer. 2018. High dimensional estimation via sum-of-squares proofs. In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018. 3389\u20133423."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.60"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993743"},{"key":"e_1_3_2_1_45_1","volume-title":"Advances in Neural Information Processing Systems","author":"Tzamos Christos","year":"2020","unstructured":"Christos Tzamos, Emmanouil-Vasileios Vlatakis-Gkaragkounis, and Ilias Zadik. 2020. Optimal Private Median Estimation under Minimal Distributional Assumptions. In Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (Eds.). 33, Curran Associates, Inc., 3301\u20133311. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2020\/file\/21d144c75af2c3a1cb90441bbb7d8b40-Paper.pdf"},{"key":"e_1_3_2_1_46_1","volume-title":"Efficiently estimating erdos-renyi graphs with node differential privacy. Advances in Neural Information Processing Systems, 32","author":"Ullman Jonathan","year":"2019","unstructured":"Jonathan Ullman and Adam Sealfon. 2019. Efficiently estimating erdos-renyi graphs with node differential privacy. Advances in Neural Information Processing Systems, 32 (2019)."},{"key":"e_1_3_2_1_47_1","unstructured":"Patrick J Wolfe and Sofia C Olhede. 2013. Nonparametric graphon estimation. arXiv preprint arXiv:1309.5936."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623642"},{"key":"e_1_3_2_1_49_1","unstructured":"Hongteng Xu Dixin Luo Lawrence Carin and Hongyuan Zha. 2020. Learning Graphons via Structured Gromov-Wasserstein Barycenters. arxiv:2012.05644."},{"key":"e_1_3_2_1_50_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning, Jennifer Dy and Andreas Krause (Eds.) (Proceedings of Machine Learning Research","volume":"5442","author":"Xu Jiaming","year":"2018","unstructured":"Jiaming Xu. 2018. Rates of Convergence of Spectral Methods for Graphon Estimation. In Proceedings of the 35th International Conference on Machine Learning, Jennifer Dy and Andreas Krause (Eds.) (Proceedings of Machine Learning Research, Vol. 80). PMLR, 5433\u20135442. https:\/\/proceedings.mlr.press\/v80\/xu18a.html"}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Vancouver BC Canada","acronym":"STOC '24"},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649643","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649643","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:47Z","timestamp":1750178207000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649643"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":50,"alternative-id":["10.1145\/3618260.3649643","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649643","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}