{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:05Z","timestamp":1750695005161,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":47,"publisher":"ACM","funder":[{"name":"Israel Science Foundation","award":["1867\\\/20"],"award-info":[{"award-number":["1867\\\/20"]}]},{"name":"NSF (National Science Foundation)","award":["DMS-2022448 and CCF-2310818"],"award-info":[{"award-number":["DMS-2022448 and CCF-2310818"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718160","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T23:34:42Z","timestamp":1750030482000},"page":"1043-1054","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3167-1766","authenticated-orcid":false,"given":"Talya","family":"Eden","sequence":"first","affiliation":[{"name":"Bar-Ilan University, Ramat-Gan, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8470-9508","authenticated-orcid":false,"given":"Reut","family":"Levi","sequence":"additional","affiliation":[{"name":"Reichman University, Herzliya, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6576-7200","authenticated-orcid":false,"given":"Dana","family":"Ron","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel-Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4353-7639","authenticated-orcid":false,"given":"Ronitt","family":"Rubinfeld","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0287-3"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1038\/nrg2102"},{"key":"e_1_3_2_1_3_1","volume-title":"Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS). 6:1\u20136:20","author":"Assadi Sepehr","year":"2019","unstructured":"Sepehr Assadi, Michael Kapralov, and Sanjeev Khanna. 2019. A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling. In Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS). 6:1\u20136:20."},{"key":"e_1_3_2_1_4_1","first-page":"1","article-title":"Asymptotically Optimal Bounds for Estimating H-Index in Sublinear Time with Applications to Subgraph Counting. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","volume":"48","author":"Assadi Sepehr","year":"2022","unstructured":"Sepehr Assadi and Hoai-An Nguyen. 2022. Asymptotically Optimal Bounds for Estimating H-Index in Sublinear Time with Applications to Subgraph Counting. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM. 48:1\u201348:20.","journal-title":"APPROX\/RANDOM."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3404867"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401898"},{"key":"e_1_3_2_1_7_1","volume-title":"Higher-order organization of complex networks. Science, 353, 6295","author":"Benson Austin R","year":"2016","unstructured":"Austin R Benson, David F Gleich, and Jure Leskovec. 2016. Higher-order organization of complex networks. Science, 353, 6295 (2016), 163\u2013166."},{"key":"e_1_3_2_1_8_1","volume-title":"Hyperedge Estimation using Polylogarithmic Subset Queries. ArXiv, abs\/1908.04196","author":"Bhattacharya Anup","year":"2019","unstructured":"Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra. 2019. Hyperedge Estimation using Polylogarithmic Subset Queries. ArXiv, abs\/1908.04196 (2019)."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-021-10043-y"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502521"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1214\/11-AOS904"},{"key":"e_1_3_2_1_12_1","first-page":"1","article-title":"On the Complexity of Triangle Counting Using Emptiness Queries. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","volume":"48","author":"Bishnu Arijit","year":"2023","unstructured":"Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra. 2023. On the Complexity of Triangle Counting Using Emptiness Queries. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM. 48:1\u201348:22.","journal-title":"APPROX\/RANDOM."},{"key":"e_1_3_2_1_13_1","first-page":"1","article-title":"Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","volume":"55","author":"Biswas Amartya Shankha","year":"2021","unstructured":"Amartya Shankha Biswas, Talya Eden, and Ronitt Rubinfeld. 2021. Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM. 55:1\u201355:19.","journal-title":"APPROX\/RANDOM."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1086\/421787"},{"key":"e_1_3_2_1_15_1","volume-title":"Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, (ICALP). 37:1\u201337:20","author":"Censor-Hillel Keren","year":"2024","unstructured":"Keren Censor-Hillel, Tomer Even, and Virginia Vassilevska Williams. 2024. Fast Approximate Counting of Cycles. In Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, (ICALP). 37:1\u201337:20."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.177"},{"key":"e_1_3_2_1_17_1","volume-title":"A Survey. ACM Computing Surveys (CSUR), 52, 1","author":"Cormode Graham","year":"2019","unstructured":"Graham Cormode and Hossein Jowhari. 2019. L_p Samplers and Their Applications: A Survey. ACM Computing Surveys (CSUR), 52, 1 (2019), Article 16, 31 pages."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M130604X"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1054389"},{"key":"e_1_3_2_1_20_1","volume-title":"Approximately counting and sampling Hamiltonian motifs in sublinear time. Arxiv, abs\/2503.09810","author":"Eden Talya","year":"2025","unstructured":"Talya Eden, Reut Levi, Dana Ron, and Ronitt Rubinfeld. 2025. Approximately counting and sampling Hamiltonian motifs in sublinear time. Arxiv, abs\/2503.09810 (2025)."},{"key":"e_1_3_2_1_21_1","first-page":"1","article-title":"Sampling Multiple Edges Efficiently. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","volume":"51","author":"Eden Talya","year":"2021","unstructured":"Talya Eden, Saleet Mossel, and Ronitt Rubinfeld. 2021. Sampling Multiple Edges Efficiently. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM. 51:1\u201351:15.","journal-title":"APPROX\/RANDOM."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977585.ch23"},{"key":"e_1_3_2_1_23_1","volume-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, (ICALP). 52:1\u201352:14","author":"Eden Talya","year":"2019","unstructured":"Talya Eden, Dana Ron, and Will Rosenbaum. 2019. The Arboricity Captures the Complexity of Sampling Edges. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, (ICALP). 52:1\u201352:14."},{"key":"e_1_3_2_1_24_1","volume-title":"Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, (ICALP). 56:1\u201356:19","author":"Eden Talya","year":"2022","unstructured":"Talya Eden, Dana Ron, and Will Rosenbaum. 2022. Almost Optimal Bounds for Sublinear-Time Sampling of k-Cliques in Bounded Arboricity Graphs. In Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, (ICALP). 56:1\u201356:19."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1159014"},{"volume-title":"Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA). 1467\u20131478","author":"Eden Talya","key":"e_1_3_2_1_26_1","unstructured":"Talya Eden, Dana Ron, and C. Seshadhri. 2020. Faster sublinear approximation of the number of k-cliques in low-arboricity graphs. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA). 1467\u20131478."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1176701"},{"key":"e_1_3_2_1_28_1","first-page":"1","article-title":"Lower Bounds for Approximating Graph Parameters via Communication Complexity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","volume":"11","author":"Eden Talya","year":"2018","unstructured":"Talya Eden and Will Rosenbaum. 2018. Lower Bounds for Approximating Graph Parameters via Communication Complexity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM. 11:1\u201311:18.","journal-title":"APPROX\/RANDOM."},{"key":"e_1_3_2_1_29_1","volume-title":"On Sampling Edges Almost Uniformly. In Symposium on Simplicity in Algorithms (SOSA). 7:1\u20137:9.","author":"Eden Talya","year":"2018","unstructured":"Talya Eden and Will Rosenbaum. 2018. On Sampling Edges Almost Uniformly. In Symposium on Simplicity in Algorithms (SOSA). 7:1\u20137:9."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704447304"},{"key":"e_1_3_2_1_31_1","volume-title":"Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, (ICALP). 45:1\u201345:13","author":"Fichtenberger Hendrik","year":"2020","unstructured":"Hendrik Fichtenberger, Mingze Gao, and Pan Peng. 2020. Sampling Arbitrary Subgraphs Exactly Uniformly in Sublinear Time. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, (ICALP). 45:1\u201345:13."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703427203"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1387061.1387065"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/100783066"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.0030118"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703436424"},{"key":"e_1_3_2_1_37_1","volume-title":"Network motifs: simple building blocks of complex networks. Science, 298, 5594","author":"Milo Ron","year":"2002","unstructured":"Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. 2002. Network motifs: simple building blocks of complex networks. Science, 298, 5594 (2002), 824\u2013827."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature03607"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10013.abs"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.032085699"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2775108"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth436"},{"volume-title":"Proceedings of the 19th international conference on World Wide Web (WWW). 861\u2013870","author":"Sala Alessandra","key":"e_1_3_2_1_43_1","unstructured":"Alessandra Sala, Lili Cao, Christo Wilson, Robert Zablit, Haitao Zheng, and Ben Y. Zhao. 2010. Measurement-calibrated graph models for social network experiments. In Proceedings of the 19th international conference on World Wide Web (WWW). 861\u2013870."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tree.2006.05.013"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1021\/cr990110s"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520059"},{"key":"e_1_3_2_1_47_1","volume-title":"Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, (ICALP). 107:1\u2013107:20","author":"T\u011btek Jakub","year":"2022","unstructured":"Jakub T\u011btek. 2022. Approximate Triangle Counting via Sampling and Fast Matrix Multiplication. In Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, (ICALP). 107:1\u2013107:20."}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Prague Czechia","acronym":"STOC '25"},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718160","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:41:10Z","timestamp":1750693270000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718160"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":47,"alternative-id":["10.1145\/3717823.3718160","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718160","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}