{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,31]],"date-time":"2026-10-31T11:03:14Z","timestamp":1793444594682,"version":"4.5.0"},"publisher-location":"New York, NY, USA","reference-count":77,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188810","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T16:15:46Z","timestamp":1529511346000},"page":"722-734","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["On approximating the number of k-cliques in sublinear time"],"prefix":"10.1145","author":[{"given":"Talya","family":"Eden","sequence":"first","affiliation":[{"name":"Tel Aviv University, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dana","family":"Ron","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[{"name":"University of California at Santa Cruz, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.16"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213560"},{"key":"e_1_3_2_2_3_1","volume-title":"Workshop on Large-scale Data Mining: Theory and Applications (LDMTA)","volume":"10","author":"Avron H.","year":"2010","unstructured":"H. Avron . 2010 . Counting triangles in large graphs using randomized matrix trace estimation . In Workshop on Large-scale Data Mining: Theory and Applications (LDMTA) , Vol. 10 . 10\u20139. H. Avron. 2010. Counting triangles in large graphs using randomized matrix trace estimation. In Workshop on Large-scale Data Mining: Theory and Applications (LDMTA), Vol. 10. 10\u20139."},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401898"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.83.056119"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1086\/421787"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403244"},{"key":"e_1_3_2_2_8_1","volume-title":"A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals of Mathematical Statistics","author":"Chernoff H.","year":"1952","unstructured":"H. Chernoff . 1952. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals of Mathematical Statistics ( 1952 ), 493\u2013507. H. Chernoff. 1952. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals of Mathematical Statistics (1952), 493\u2013507."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"crossref","unstructured":"N. Chiba and T. Nishizeki. 1985.  N. Chiba and T. Nishizeki. 1985.","DOI":"10.2208\/jscej.1985.356_499"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_3_2_2_11_1","unstructured":"F. Chierichetti A. Dasgupta R. Kumar S. Lattanzi and T. Sarlos. 2016.  F. Chierichetti A. Dasgupta R. Kumar S. Lattanzi and T. Sarlos. 2016."},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872427.2883045"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020513"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1086\/228943"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703435297"},{"key":"e_1_3_2_2_16_1","unstructured":"A. Czumaj and C. Sohler. 2009.  A. Czumaj and C. Sohler. 2009."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/060672121"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2566486.2568019"},{"key":"e_1_3_2_2_19_1","unstructured":"J. P. Eckmann and E. Moses. 2002.  J. P. Eckmann and E. Moses. 2002."},{"key":"e_1_3_2_2_20_1","volume-title":"Co-links Uncovers Hidden Thematic Layers in the World Wide Web. Proceedings of the National Academy of Sciences 99","author":"Curvature","year":"2002","unstructured":"Curvature of Co-links Uncovers Hidden Thematic Layers in the World Wide Web. Proceedings of the National Academy of Sciences 99 , 9 ( 2002 ), 5825\u20135829. Curvature of Co-links Uncovers Hidden Thematic Layers in the World Wide Web. Proceedings of the National Academy of Sciences 99, 9 (2002), 5825\u20135829."},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.44"},{"key":"e_1_3_2_2_22_1","unstructured":"T. Eden D. Ron and C. Seshadhri. 2017.  T. Eden D. Ron and C. Seshadhri. 2017."},{"key":"e_1_3_2_2_23_1","volume-title":"CoRR abs\/1707.04858v1","author":"Sublinear Time On Approximating","year":"2017","unstructured":"On Approximating the Number of k-cliques in Sublinear Time . CoRR abs\/1707.04858v1 ( 2017 ). arXiv: 1707.04858v1 http:\/\/arxiv.org\/abs\/1707.04858v1 On Approximating the Number of k-cliques in Sublinear Time. CoRR abs\/1707.04858v1 (2017). arXiv: 1707.04858v1 http:\/\/arxiv.org\/abs\/1707.04858v1"},{"key":"e_1_3_2_2_24_1","volume-title":"44th International Colloquium on Automata, Languages, and Programming, ICALP 2017","author":"Eden T.","year":"2017","unstructured":"T. Eden , D. Ron , and C. Seshadhri . 2017. Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 , July 10-14, 2017 , Warsaw, Poland. 7:1\u20137:13. T. Eden, D. Ron, and C. Seshadhri. 2017. Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland. 7:1\u20137:13."},{"key":"e_1_3_2_2_25_1","unstructured":"T. Eden and W. Rosenbaum. 2017.  T. Eden and W. Rosenbaum. 2017."},{"key":"e_1_3_2_2_26_1","volume-title":"CoRR abs\/1709.04262","author":"Approximating Graph Lower Bounds","year":"2017","unstructured":"Lower Bounds for Approximating Graph Parameters via Communication Complexity . CoRR abs\/1709.04262 ( 2017 ). Lower Bounds for Approximating Graph Parameters via Communication Complexity. CoRR abs\/1709.04262 (2017)."},{"key":"e_1_3_2_2_27_1","unstructured":"arXiv: 1709.04262 http:\/\/arxiv.org\/abs\/1709.04262  arXiv: 1709.04262 http:\/\/arxiv.org\/abs\/1709.04262"},{"key":"e_1_3_2_2_28_1","unstructured":"T. Eden and W. Rosenbaum. 2018.  T. Eden and W. Rosenbaum. 2018."},{"key":"e_1_3_2_2_29_1","volume-title":"Sampling Edges Almost Uniformly. In 1st Symposium on Simplicity in Algorithms, SOSA 2018","author":"On","year":"2018","unstructured":"On Sampling Edges Almost Uniformly. In 1st Symposium on Simplicity in Algorithms, SOSA 2018 , January 7-10, 2018 , New Orleans, LA, USA. 7:1\u20137:9. On Sampling Edges Almost Uniformly. In 1st Symposium on Simplicity in Algorithms, SOSA 2018, January 7-10, 2018, New Orleans, LA, USA. 7:1\u20137:9."},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.05.009"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2543629"},{"key":"e_1_3_2_2_32_1","unstructured":"U. Feige. 2006.  U. Feige. 2006."},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704447304"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2794080"},{"key":"e_1_3_2_2_35_1","unstructured":"B. Foucault Welles A. Van Devender and N. Contractor. 2010.  B. Foucault Welles A. Van Devender and N. Contractor. 2010."},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1753846.1754097"},{"key":"e_1_3_2_2_37_1","unstructured":"O. Goldreich. 2017.  O. Goldreich. 2017."},{"key":"e_1_3_2_2_38_1","unstructured":"Introduction to Property Testing. Cambridge University Press.  Introduction to Property Testing. Cambridge University Press."},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/1387061.1387065"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/100783066"},{"key":"e_1_3_2_2_41_1","unstructured":"On Approximating the Number of k-Cliques in Sublinear Time STOC\u201918 June 25\u201329 2018 Los Angeles CA USA  On Approximating the Number of k-Cliques in Sublinear Time STOC\u201918 June 25\u201329 2018 Los Angeles CA USA"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.77"},{"key":"e_1_3_2_2_43_1","unstructured":"P. W. Holland and S. Leinhardt. 1970.  P. W. Holland and S. Leinhardt. 1970."},{"key":"e_1_3_2_2_44_1","volume-title":"492\u2013513","author":"Amer A","year":"1970","unstructured":"A method for detecting structure in sociometric data. Amer . J. Sociology 76 ( 1970 ), 492\u2013513 . A method for detecting structure in sociometric data. Amer. J. Sociology 76 (1970), 492\u2013513."},{"key":"e_1_3_2_2_45_1","unstructured":"M. O. Jackson T. Rodriguez-Barraquer and X. Tan. 2012.  M. O. Jackson T. Rodriguez-Barraquer and X. Tan. 2012."},{"key":"e_1_3_2_2_46_1","volume-title":"Network Patterns of Favor Exchange. American Economic Review 102, 5","author":"Capital Social","year":"2012","unstructured":"Social Capital and Social Quilts : Network Patterns of Favor Exchange. American Economic Review 102, 5 ( 2012 ), 1857?1897. Social Capital and Social Quilts: Network Patterns of Favor Exchange. American Economic Review 102, 5 (2012), 1857?1897."},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052636"},{"key":"e_1_3_2_2_48_1","unstructured":"H. Jowhari and M. Ghodsi. 2005.  H. Jowhari and M. Ghodsi. 2005."},{"key":"e_1_3_2_2_49_1","volume-title":"Proceedings of the International Conference Computing and Combinatorics (COCOON). Springer, 710\u2013716","author":"New","unstructured":"New streaming algorithms for counting triangles in graphs . In Proceedings of the International Conference Computing and Combinatorics (COCOON). Springer, 710\u2013716 . New streaming algorithms for counting triangles in graphs. In Proceedings of the International Conference Computing and Combinatorics (COCOON). Springer, 710\u2013716."},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_53"},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2012.625260"},{"key":"e_1_3_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1497290.1497298"},{"key":"e_1_3_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.18637\/jss.v011.i03"},{"key":"e_1_3_2_2_54_1","unstructured":"R. Milo S. Shen-Orr S. Itzkovitz N. Kashtan D. Chklovskii and U. Alon. 2002.  R. Milo S. Shen-Orr S. Itzkovitz N. Kashtan D. Chklovskii and U. Alon. 2002."},{"key":"e_1_3_2_2_55_1","volume-title":"simple building blocks of complex networks. Science 298, 5594","author":"Network","year":"2002","unstructured":"Network motifs : simple building blocks of complex networks. Science 298, 5594 ( 2002 ), 824\u2013827. Network motifs: simple building blocks of complex networks. Science 298, 5594 (2002), 824\u2013827."},{"key":"e_1_3_2_2_56_1","unstructured":"J. Ne\u0161t\u0159il and S. Poljak. 1985.  J. Ne\u0161t\u0159il and S. Poljak. 1985."},{"key":"e_1_3_2_2_57_1","volume-title":"Commentationes Mathematicae Universitatis Carolinae 26, 2","author":"On","year":"1985","unstructured":"On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae 26, 2 ( 1985 ), 415\u2013419. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae 26, 2 (1985), 415\u2013419."},{"key":"e_1_3_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.81"},{"key":"e_1_3_2_2_59_1","volume-title":"Proceedings of the Symposium on Discrete Algorithms (SODA). 1123\u20131131","author":"Onak K.","unstructured":"K. Onak , D. Ron , M. Rosen , and R. Rubinfeld . 2012. A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size . In Proceedings of the Symposium on Discrete Algorithms (SODA). 1123\u20131131 . K. Onak, D. Ron, M. Rosen, and R. Rubinfeld. 2012. A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. In Proceedings of the Symposium on Discrete Algorithms (SODA). 1123\u20131131."},{"key":"e_1_3_2_2_60_1","unstructured":"M. Parnas and D. Ron. 2007.  M. Parnas and D. Ron. 2007."},{"key":"e_1_3_2_2_61_1","volume-title":"Theoretical Computer Science 381, 1-3","author":"Approximating","year":"2007","unstructured":"Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. Theoretical Computer Science 381, 1-3 ( 2007 ), 183\u2013196. Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. Theoretical Computer Science 381, 1-3 (2007), 183\u2013196."},{"key":"e_1_3_2_2_62_1","volume-title":"Social Capital: Its Origins and Applications in Modern Sociology","author":"Portes Alejandro","year":"2000","unstructured":"Alejandro Portes . 2000 . Social Capital: Its Origins and Applications in Modern Sociology . In Knowledge and Social Capital, Eric L. Lesser (Ed.). Butterworth-Heinemann , Boston , 43 \u2013 67. 0- 7506- 7222- 1.50006- 4 Alejandro Portes. 2000. Social Capital: Its Origins and Applications in Modern Sociology. In Knowledge and Social Capital, Eric L. Lesser (Ed.). Butterworth-Heinemann, Boston, 43 \u2013 67. 0- 7506- 7222- 1.50006- 4"},{"key":"e_1_3_2_2_63_1","unstructured":"T. Schank and D. Wagner. 2005.  T. Schank and D. Wagner. 2005."},{"key":"e_1_3_2_2_64_1","volume-title":"Journal of Graph Algorithms and Applications 9","author":"Coefficient Approximating Clustering","year":"2005","unstructured":"Approximating Clustering Coefficient and Transitivity. Journal of Graph Algorithms and Applications 9 ( 2005 ), 265\u2013275. Issue 2. Approximating Clustering Coefficient and Transitivity. Journal of Graph Algorithms and Applications 9 (2005), 265\u2013275. Issue 2."},{"key":"e_1_3_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/11427186_54"},{"key":"e_1_3_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.85.056109"},{"key":"e_1_3_2_2_67_1","volume-title":"Proceedings of the International Conference on Data Mining (ICDM)","volume":"4","author":"Seshadhri C.","unstructured":"C. Seshadhri , A. Pinar , and T. G. Kolda . 2013. Fast Triangle Counting through Wedge Sampling. arXiv:1202.5230 . In Proceedings of the International Conference on Data Mining (ICDM) , Vol. 4 . 5. http:\/\/arxiv.org\/abs\/1202.5230 C. Seshadhri, A. Pinar, and T. G. Kolda. 2013. Fast Triangle Counting through Wedge Sampling. arXiv:1202.5230. In Proceedings of the International Conference on Data Mining (ICDM), Vol. 4. 5. http:\/\/arxiv.org\/abs\/1202.5230"},{"key":"e_1_3_2_2_68_1","unstructured":"S. Suri and S. Vassilvitskii. 2011.  S. Suri and S. Vassilvitskii. 2011."},{"key":"e_1_3_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963491"},{"key":"e_1_3_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505741"},{"key":"e_1_3_2_2_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.72"},{"key":"e_1_3_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_3_2_2_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557111"},{"key":"e_1_3_2_2_74_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00245"},{"key":"e_1_3_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.10.014"},{"key":"e_1_3_2_2_76_1","doi-asserted-by":"publisher","DOI":"10.1049\/el:19740097"},{"key":"e_1_3_2_2_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/355744.355749"}],"event":{"name":"STOC '18: Symposium on Theory of Computing","location":"Los Angeles CA USA","acronym":"STOC '18","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188810","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188810","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:07:09Z","timestamp":1750198029000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188810"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":77,"alternative-id":["10.1145\/3188745.3188810","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188810","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}