{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:38Z","timestamp":1750220618733,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,10,10]],"date-time":"2022-10-10T00:00:00Z","timestamp":1665360000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["IIS-1838154, CCF-1703925, CCF-1814873, and CCF-1563155"],"award-info":[{"award-number":["IIS-1838154, CCF-1703925, CCF-1814873, and CCF-1563155"]}]},{"name":"Simons Collaboration on Algorithms and Geometry"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>\n            We consider the problem of finding a cycle in a sparse directed graph\n            <jats:italic>G<\/jats:italic>\n            that is promised to be far from acyclic, meaning that the smallest\n            <jats:italic>feedback arc set<\/jats:italic>\n            , i.e., a subset of edges whose deletion results in an acyclic graph, in\n            <jats:italic>G<\/jats:italic>\n            is large. We prove an information-theoretic lower bound, showing that for\n            <jats:italic>N<\/jats:italic>\n            -vertex graphs with constant outdegree, any algorithm for this problem must make \u03a9\u0304(N\n            <jats:sup>5\/9<\/jats:sup>\n            ) queries to an adjacency list representation of\n            <jats:italic>G<\/jats:italic>\n            . In the language of property testing, our result is an \u03a9\u0304(N\n            <jats:sup>5\/9)<\/jats:sup>\n            lower bound on the query complexity of one-sided algorithms for testing whether sparse digraphs with constant outdegree are far from acyclic. This is the first improvement on the \u03a9 (\u221a\n            <jats:italic>N<\/jats:italic>\n            ) lower bound, implicit in the work of Bender and Ron, which follows from a simple birthday paradox argument.\n          <\/jats:p>","DOI":"10.1145\/3417979","type":"journal-article","created":{"date-parts":[[2022,2,8]],"date-time":"2022-02-08T22:18:47Z","timestamp":1644358727000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Lower Bound on Cycle-Finding in Sparse Digraphs"],"prefix":"10.1145","volume":"18","author":[{"given":"Xi","family":"Chen","sequence":"first","affiliation":[{"name":"Columbia University, New York, NY, USA"}]},{"given":"Tim","family":"Randolph","sequence":"additional","affiliation":[{"name":"Columbia University, New York, NY, USA"}]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[{"name":"Columbia University, New York, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5994-8838","authenticated-orcid":false,"given":"Timothy","family":"Sun","sequence":"additional","affiliation":[{"name":"Columbia University, New York, NY, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,10,10]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0287-3"},{"key":"e_1_3_2_3_2","first-page":"6:1\u20136:20","volume-title":"10th Innovations in Theoretical Computer Science Conference (ITCS)","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 10th Innovations in Theoretical Computer Science Conference (ITCS). 6:1\u20136:20."},{"key":"e_1_3_2_4_2","volume-title":"Proceedings of the 2018 ACM Conference on Innovations in Theoretical Computer Science","author":"Beame Paul","year":"2018","unstructured":"Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, and Makrand Sinha. 2018. Edge estimation with independent set oracles. In Proceedings of the 2018 ACM Conference on Innovations in Theoretical Computer Science."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10023.abs"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374433"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403244"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703435297"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20462"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897575"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/060672121"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1054389"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188810"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704447304"},{"key":"e_1_3_2_15_2","doi-asserted-by":"crossref","unstructured":"Jacob Fox. 2018. Personal communication.","DOI":"10.5465\/AMBPP.2018.10929abstract"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781108135252"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0078-7"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/1387061.1387065"},{"issue":"3","key":"e_1_3_2_19_2","first-page":"1365","article-title":"Counting stars and other small subgraphs in sublinear-time","volume":"25","author":"Gonen Mira","year":"2011","unstructured":"Mira Gonen, Dana Ron, and Yuval Shavitt. 2011. Counting stars and other small subgraphs in sublinear-time. SIAM J. Comput. 25, 3 (2011), 1365\u20131411.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_2_20_2","first-page":"22","volume-title":"Proc. 50th IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Hassidim Avinatan","year":"2009","unstructured":"Avinatan Hassidim, Jonathan A. Kelner, Huy N. Nguyen, and Krzysztof Onak. 2009. Local graph partitions for approximation and testing. In Proc. 50th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, 22\u201331."},{"key":"e_1_3_2_21_2","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1007\/978-3-642-33090-2_52","volume-title":"Algorithms - ESA 2012-20th Annual European Symposium","author":"Hellweg Frank","year":"2012","unstructured":"Frank Hellweg and Christian Sohler. 2012. Property testing in sparse directed graphs: Strong connectivity and subgraph-freeness. In Algorithms - ESA 2012-20th Annual European Symposium. 599\u2013610."},{"key":"e_1_3_2_22_2","article-title":"Property-testing in sparse directed graphs: 3-star-freeness and connectivity","volume":"1312","author":"Hellweg Frank","year":"2013","unstructured":"Frank Hellweg and Christian Sohler. 2013. Property-testing in sparse directed graphs: 3-star-freeness and connectivity. CoRR abs\/1312.0497.","journal-title":"CoRR"},{"key":"e_1_3_2_23_2","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1109\/FOCS.2018.00055","volume-title":"59th IEEE Annual Symposium on Foundations of Computer Science (FOCS)","author":"Kumar Akash","year":"2018","unstructured":"Akash Kumar, C. Seshadhri, and Andrew Stolman. 2018. Finding forbidden minors in sublinear time: A \\( n^{1\/2+o(1)} \\) -query one-sided tester for minor closed properties on bounded degree graphs. In 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS). 509\u2013520."},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316330"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1497290.1497298"},{"key":"e_1_3_2_26_2","first-page":"327","volume-title":"Proc. 49th IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Nguyen Huy N.","year":"2008","unstructured":"Huy N. Nguyen and Krzysztof Onak. 2008. Constant-time approximation algorithms via local improvements. In Proc. 49th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, 327\u2013336."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.88"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.06.038"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.5555\/1280283.1280327"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02582932"},{"key":"e_1_3_2_31_2","first-page":"222","volume-title":"Proc. Seventeenth Annual Symposium on Foundations of Computer Science (STOC)","author":"Yao A.","year":"1977","unstructured":"A. Yao. 1977. Probabilistic computations: Towards a unified measure of complexity. In Proc. Seventeenth Annual Symposium on Foundations of Computer Science (STOC). 222\u2013227."},{"key":"e_1_3_2_32_2","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1145\/1536414.1536447","volume-title":"Proc. 41st Annual ACM Symposium on Theory of Computing (STOC)","author":"Yoshida Yuichi","year":"2009","unstructured":"Yuichi Yoshida, Masaki Yamamoto, and Hiro Ito. 2009. An improved constant-time approximation algorithm for maximum matchings. In Proc. 41st Annual ACM Symposium on Theory of Computing (STOC). ACM, 225\u2013234."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3417979","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3417979","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3417979","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:14Z","timestamp":1750197674000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3417979"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,10]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3417979"],"URL":"https:\/\/doi.org\/10.1145\/3417979","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2022,10,10]]},"assertion":[{"value":"2020-01-26","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-08-13","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}