{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,15]],"date-time":"2025-12-15T10:04:17Z","timestamp":1765793057591,"version":"3.48.0"},"reference-count":30,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2025,12,31]]},"DOI":"10.1137\/24m1653173","type":"journal-article","created":{"date-parts":[[2025,12,15]],"date-time":"2025-12-15T10:00:16Z","timestamp":1765792816000},"page":"1626-1642","source":"Crossref","is-referenced-by-count":0,"title":["Testing Graph Properties with the Container Method"],"prefix":"10.1137","volume":"54","author":[{"given":"Eric","family":"Blais","sequence":"first","affiliation":[{"name":"David R. Cheriton School of Computer Science, University of Waterloo, Waterloo N2L 5Z5, ON, Canada."}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-7008-5441","authenticated-orcid":true,"given":"Cameron","family":"Seth","sequence":"additional","affiliation":[{"name":"David R. Cheriton School of Computer Science, University of Waterloo, Waterloo N2L 5Z5, ON, Canada."}]}],"member":"351","published-online":{"date-parts":[[2025,12,15]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070001"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199358655"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-2014-00816-X"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-16-8622-1"},{"key":"ref5","doi-asserted-by":"crossref","unstructured":"E. Blais and C. Seth, New graph and hypergraph container lemmas with applications in property testing, in Proceedings of the 56th Annual ACM SIGACT Symposium on Theory of Computing, ACM, 2024, pp. 1793\u20131804.","DOI":"10.1145\/3618260.3649708"},{"key":"ref6","unstructured":"A. Bogdanov and F. Li, A Better Tester for Bipartiteness? preprint, https:\/\/arxiv.org\/abs\/1011.0531, 2010."},{"key":"ref7","doi-asserted-by":"crossref","unstructured":"A. Bogdanov and L. Trevisan, Lower bounds for testing bipartiteness in dense graphs, in Proceedings of the 19th IEEE Annual Conference on Computational Complexity, IEEE, 2004, pp. 75\u201381.","DOI":"10.1109\/CCC.2004.1313803"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70495-3"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703431391"},{"key":"ref10","unstructured":"U. Feige and M. Seltser, On the Densest, \\(k\\)-Subgraph Problem, Technical report CS97-16, Weizmann Institute of Science, 1997."},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1017\/9781108135252"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1137\/090749621"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10078"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"O. Goldreich and A. Wigderson, Non-adaptive vs adaptive queries in the dense graph testing model, in Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, IEEE, 2021, pp. 269\u2013275.","DOI":"10.1109\/FOCS52979.2021.00035"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9237-4"},{"key":"ref17","first-page":"1","volume":"25","author":"Huleihel W.","year":"2024","journal-title":"J. Mach. Learn. Res."},{"key":"ref18","doi-asserted-by":"crossref","unstructured":"M. Jenssen, W. Perkins, and A. Potukuchi, Approximately counting independent sets in bipartite graphs via graph containers, Random Structures Algorithms, 63 (2023), pp. 215\u2013241.","DOI":"10.1002\/rsa.21145"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9574.1980.tb00681.x"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(82)90204-7"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"P. Manurangsi, Almost-polynomial ratio ETH-hardness of approximating densest, \\(k\\)-subgraph, in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, ACM, 2017, pp. 954\u2013961.","DOI":"10.1145\/3055399.3055412"},{"key":"ref22","volume":"1","author":"Mulzer W.","year":"2018","journal-title":"Bulletin of EATCS"},{"key":"ref23","series-title":"Leibniz International Proceedings in Informatics 116","first-page":"53:1","volume-title":"in Approximation, Randomization, and Combinatorial Optimization,\u00a0Algorithms and Techniques (APPROX\/RANDOM","volume":"2018","author":"Nakar Y.","year":"2018"},{"key":"ref24","first-page":"29","volume":"19","author":"Neumann P.","year":"1970","journal-title":"Wiss. Z.Tech. Univ. Dresden"},{"key":"ref25","volume":"17","author":"R\u00e1cz M. Z.","year":"2020","journal-title":"ALEA Lat. Am. J. Probab. Math. Stat."},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/BF02582932"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1007\/11571155_1"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-014-0562-8"},{"key":"ref29","doi-asserted-by":"crossref","unstructured":"C. Sohler, Almost optimal canonical property testers for satisfiability, in Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2012, pp. 541\u2013550.","DOI":"10.1109\/FOCS.2012.59"},{"key":"ref30","doi-asserted-by":"crossref","unstructured":"O. Zamir, Algorithmic applications of hypergraph and partition containers, in Proceedings of the 55th Annual ACM Symposium on Theory of Computing, ACM, 2023 pp. 985\u2013998.","DOI":"10.1145\/3564246.3585163"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,12,15]],"date-time":"2025-12-15T10:00:23Z","timestamp":1765792823000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1653173"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,15]]},"references-count":30,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,31]]}},"alternative-id":["10.1137\/24M1653173"],"URL":"https:\/\/doi.org\/10.1137\/24m1653173","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,15]]}}}