{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:18:54Z","timestamp":1778807934831,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662439470","type":"print"},{"value":"9783662439487","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_19","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T16:10:36Z","timestamp":1402503036000},"page":"223-234","source":"Crossref","is-referenced-by-count":31,"title":["Listing Triangles"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Bj\u00f6rklund","sequence":"first","affiliation":[]},{"given":"Rasmus","family":"Pagh","sequence":"additional","affiliation":[]},{"given":"Virginia Vassilevska","family":"Williams","sequence":"additional","affiliation":[]},{"given":"Uri","family":"Zwick","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"Afrati, F.N., Fotakis, D., Ullman, J.D.: Enumerating subgraph instances using Map-Reduce. In: Proc.\u00a0IEEE International Conference on Data Engineering (ICDE), pp. 62\u201373 (2013)","DOI":"10.1109\/ICDE.2013.6544814"},{"issue":"4","key":"19_CR2","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N. Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM\u00a042(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"issue":"2","key":"19_CR3","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/1921659.1921670","volume":"7","author":"Y. Aumann","year":"2011","unstructured":"Aumann, Y., Lewenstein, M., Lewenstein, N., Tsur, D.: Finding witnesses by peeling. ACM Transactions on Algorithms\u00a07(2), 24 (2011)","journal-title":"ACM Transactions on Algorithms"},{"key":"19_CR4","doi-asserted-by":"crossref","unstructured":"Berry, J., Fostvedt, L., Nordman, D., Phillips, C., Seshadhri, C., Wilson, A.: Why do simple algorithms for triangle enumeration work in the real world? In: Proc.\u00a0Innovations in Theoretical Computer Science (2014)","DOI":"10.1145\/2554797.2554819"},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"Berry, J.W., Hendrickson, B., LaViolette, R.A., Phillips, C.A.: Tolerating the community detection resolution limit with edge weighting. Phys. Rev. E\u00a083, 056119 (2011)","DOI":"10.1103\/PhysRevE.83.056119"},{"key":"19_CR6","doi-asserted-by":"crossref","unstructured":"Chu, S., Cheng, J.: Triangle listing in massive networks. ACM Trans. Knowl. Discov. Data\u00a06(4), 17:1\u201317:32 (2012)","DOI":"10.1145\/2382577.2382581"},{"key":"19_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1007\/3-540-45539-6_27","volume-title":"Advances in Cryptology - EUROCRYPT 2000","author":"N. Courtois","year":"2000","unstructured":"Courtois, N., Klimov, A., Patarin, J., Shamir, A.: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol.\u00a01807, pp. 392\u2013407. Springer, Heidelberg (2000)"},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"Welles, B.F., Van Devender, A., Contractor, N.: Is a friend a friend? Investigating the structure of friendship networks in virtual worlds. In: CHI 2010 Extended Abstracts on Human Factors in Computing Systems, pp. 4027\u20134032. ACM (2010)","DOI":"10.1145\/1753846.1754097"},{"issue":"4","key":"19_CR9","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1016\/j.ipl.2008.10.012","volume":"109","author":"L. Gasieniec","year":"2009","unstructured":"Gasieniec, L., Kowaluk, M., Lingas, A.: Faster multi-witnesses for boolean matrix multiplication. Inf. Process. Lett.\u00a0109(4), 242\u2013247 (2009)","journal-title":"Inf. Process. Lett."},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"Hu, X., Tao, Y., Chung, C.-W.: Massive graph triangulation. In: Proc.\u00a0of SIGMOD, pp. 325\u2013336. ACM (2013)","DOI":"10.1145\/2463676.2463704"},{"issue":"2","key":"19_CR11","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1006\/jcom.1998.0476","volume":"14","author":"X. Huang","year":"1998","unstructured":"Huang, X., Pan, V.Y.: Fast rectangular matrix multiplication and applications. J. of Complexity\u00a014(2), 257\u2013299 (1998)","journal-title":"J. of Complexity"},{"key":"19_CR12","unstructured":"Indyk, P.: Explicit constructions for compressed sensing of sparse signals. In: Proc. of 19th SODA, pp. 30\u201333 (2008)"},{"issue":"4","key":"19_CR13","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0207033","volume":"7","author":"A. Itai","year":"1978","unstructured":"Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. SIAM Journal on Computing\u00a07(4), 413\u2013423 (1978)","journal-title":"SIAM Journal on Computing"},{"key":"19_CR14","unstructured":"Jafargholi, Z., Viola, E.: 3SUM, 3XOR, triangles. CoRR, abs\/1305.3827 (2013)"},{"key":"19_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/3-540-48405-1_2","volume-title":"Advances in Cryptology - CRYPTO \u201999","author":"A. Kipnis","year":"1999","unstructured":"Kipnis, A., Shamir, A.: Cryptanalysis of the HFE public key cryptosystem by relinearization. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol.\u00a01666, pp. 19\u201330. Springer, Heidelberg (1999)"},{"issue":"1-2","key":"19_CR16","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1080\/15427951.2012.625260","volume":"8","author":"M.N. Kolountzakis","year":"2012","unstructured":"Kolountzakis, M.N., Miller, G.L., Peng, R., Tsourakakis, C.E.: Efficient triangle counting in large graphs via degree-based vertex partitioning. Internet Mathematics\u00a08(1-2), 161\u2013185 (2012)","journal-title":"Internet Mathematics"},{"key":"19_CR17","doi-asserted-by":"publisher","first-page":"89","DOI":"10.2307\/4145212","volume":"111","author":"S. Landau","year":"2004","unstructured":"Landau, S.: Polynomials in the nation\u2019s service: using algebra to design the advanced encryption standard. American Mathematical Monthly\u00a0111, 89\u2013117 (2004)","journal-title":"American Mathematical Monthly"},{"key":"19_CR18","doi-asserted-by":"crossref","unstructured":"Le Gall, F.: Powers of tensors and fast matrix multiplication. CoRR, abs:1401.7714 (2014)","DOI":"10.1145\/2608628.2608664"},{"key":"19_CR19","doi-asserted-by":"crossref","unstructured":"Gall, F.L.: Faster algorithms for rectangular matrix multiplication. In: Proc.\u00a0Foundations of Computer Science, pp. 514\u2013523 (2012)","DOI":"10.1109\/FOCS.2012.80"},{"key":"19_CR20","doi-asserted-by":"crossref","unstructured":"Pagh, R., Silvestri, F.: The input\/output complexity of triangle enumeration. arXiv preprint arXiv:1312.0723 (2013)","DOI":"10.1145\/2594538.2594552"},{"key":"19_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1007\/3-540-44750-4_20","volume-title":"Advances in Cryptology - CRYPTO \u201995","author":"J. Patarin","year":"1995","unstructured":"Patarin, J.: Cryptoanalysis of the matsumoto and imai public key scheme of eurocrypt\u201988. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol.\u00a0963, pp. 248\u2013261. Springer, Heidelberg (1995)"},{"key":"19_CR22","doi-asserted-by":"crossref","unstructured":"Porat, E., Strauss, M.J.: Sublinear time, measurement-optimal, sparse recovery for all. In: Proc. of 23rd SODA, pp. 1215\u20131227. SIAM (2012)","DOI":"10.1137\/1.9781611973099.96"},{"key":"19_CR23","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M.: Towards polynomial lower bounds for dynamic problems. In: Proc. of 42nd STOC, pp. 603\u2013610 (2010)","DOI":"10.1145\/1806689.1806772"},{"key":"19_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1007\/11427186_54","volume-title":"Experimental and Efficient Algorithms","author":"T. Schank","year":"2005","unstructured":"Schank, T., Wagner, D.: Finding, counting and listing all triangles in large graphs, an experimental study. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol.\u00a03503, pp. 606\u2013609. Springer, Heidelberg (2005)"},{"issue":"2","key":"19_CR25","doi-asserted-by":"crossref","first-page":"58","DOI":"10.14778\/1921071.1921073","volume":"4","author":"N. Wang","year":"2010","unstructured":"Wang, N., Zhang, J., Tan, K.-L., Tung, A.K.: On triangulation-based dense neighborhood graph discovery. Proc.\u00a0VLDB Endowment\u00a04(2), 58\u201368 (2010)","journal-title":"Proc.\u00a0VLDB Endowment"},{"key":"19_CR26","doi-asserted-by":"crossref","unstructured":"Williams, V.V.: Multiplying matrices faster than coppersmith-winograd. In: Proc. of 44nd STOC, pp. 887\u2013898 (2012)","DOI":"10.1145\/2213977.2214056"},{"key":"19_CR27","doi-asserted-by":"crossref","unstructured":"Williams, V.V., Williams, R.: Subcubic equivalences between path, matrix and triangle problems. In: Proc.\u00a0IEEE Foundations of Computer Science (FOCS), pp. 645\u2013654 (2010)","DOI":"10.1109\/FOCS.2010.67"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T09:31:09Z","timestamp":1746264669000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}