{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:29:33Z","timestamp":1750220973300,"version":"3.41.0"},"publisher-location":"New York, New York, USA","reference-count":29,"publisher":"ACM Press","license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF TRIPODS","award":["CCF-1740850"],"award-info":[{"award-number":["CCF-1740850"]}]},{"name":"NSF","award":["CCF-1618981, CCF-1813165"],"award-info":[{"award-number":["CCF-1618981, CCF-1813165"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1145\/3313276.3316330","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"559-567","source":"Crossref","is-referenced-by-count":5,"title":["Random walks and forbidden minors II"],"prefix":"10.1145","author":[{"given":"Akash","family":"Kumar","sequence":"first","affiliation":[{"name":"Purdue University, USA"}]},{"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[{"name":"University of California at Santa Cruz, USA"}]},{"given":"Andrew","family":"Stolman","sequence":"additional","affiliation":[{"name":"University of California at Santa Cruz, USA"}]}],"member":"320","reference":[{"key":"key-10.1145\/3313276.3316330-1","unstructured":"Noga Alon, Paul Seymour, and Robin Thomas. 1990. A separator theorem for nonplanar graphs. Journal of the American Mathematical Society 3, 4 (1990), 801&#8211;808."},{"key":"key-10.1145\/3313276.3316330-2","doi-asserted-by":"crossref","unstructured":"I. Benjamini, O. Schramm, and A. Shapira. 2008. Every Minor-Closed Property of Sparse Graphs is Testable. In Symposium on the Theory of Computing (STOC). 393&#8211;402.","DOI":"10.1145\/1374376.1374433"},{"key":"#cr-split#-key-10.1145\/3313276.3316330-3.1","unstructured":"Artur Czumaj, Oded Goldreich, Dana Ron, C Seshadhri, Asaf Shapira, and Christian Sohler. 2014. Finding cycles and trees in sublinear time. Random Structures &#38;amp"},{"key":"#cr-split#-key-10.1145\/3313276.3316330-3.2","doi-asserted-by":"crossref","unstructured":"Algorithms 45, 2 (2014), 139&#8211;184.","DOI":"10.3917\/inso.184.0139"},{"key":"key-10.1145\/3313276.3316330-4","doi-asserted-by":"crossref","unstructured":"Reinhard Diestel. 2010. Graph Theory, Fourth Edition. Springer.","DOI":"10.1007\/978-3-642-14279-6"},{"key":"key-10.1145\/3313276.3316330-5","doi-asserted-by":"crossref","unstructured":"D. P. Dubhashi and A. Panconesi. 2009. Concentration of measure for the analysis of randomized algorithms. Cambridge.","DOI":"10.1017\/CBO9780511581274"},{"key":"key-10.1145\/3313276.3316330-6","doi-asserted-by":"crossref","unstructured":"Alan Edelman, Avinatan Hassidim, Huy N. Nguyen, and Krzysztof Onak. 2011. An E&#983951;cient Partitioning Oracle for Bounded-Treewidth Graphs. In Workshop on Randomization and Computation (RANDOM). 530&#8211;541.","DOI":"10.1007\/978-3-642-22935-0_45"},{"key":"key-10.1145\/3313276.3316330-7","unstructured":"Hendrik Fichtenberger, Reut Levi, Yadu Vasudev, and Maximilian W&#246;tzel. 2017. On Testing Minor-Freeness in Bounded Degree Graphs With One-Sided Error. CoRR abs\/1707.06126 (2017)."},{"key":"key-10.1145\/3313276.3316330-8","doi-asserted-by":"crossref","unstructured":"O. Goldreich. 2017. Introduction to Property Testing. Cambridge University Press.","DOI":"10.1017\/9781108135252"},{"key":"key-10.1145\/3313276.3316330-9","unstructured":"O. Goldreich and D. Ron. 1999. A Sublinear Bipartite Tester for Bounded Degree Graphs. Combinatorica 19, 3 (1999), 335&#8211;373."},{"key":"key-10.1145\/3313276.3316330-10","unstructured":"O. Goldreich and D. Ron. 2002. Property Testing in Bounded Degree Graphs. Algorithmica 32, 2 (2002), 302&#8211;343."},{"key":"key-10.1145\/3313276.3316330-11","unstructured":"A. Hassidim, J. Kelner, H. Nguyen, and K. Onak. 2009. Local Graph Partitions for Approximation and Testing, In Foundations of Computer Science (FOCS). Proc. of 50th FOCS, 22&#8211;31."},{"key":"key-10.1145\/3313276.3316330-12","unstructured":"John Hopcroft and Robert Tarjan. 1974. E&#983951;cient planarity testing. Journal of the ACM (JACM) 21, 4 (1974), 549&#8211;568."},{"key":"key-10.1145\/3313276.3316330-13","unstructured":"Satyen Kale, Yuval Peres, and C. Seshadhri. 2013. Noise Tolerance of Expanders and Sublinear Expansion Reconstruction. SIAM J. Comput. 42, 1 (2013), 305&#8211;323."},{"key":"key-10.1145\/3313276.3316330-14","unstructured":"Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Bruce A. Reed. 2012. The disjoint paths problem in quadratic time. J. Comb. Theory, Ser. B 102, 2 (2012), 424&#8211;435."},{"key":"key-10.1145\/3313276.3316330-15","doi-asserted-by":"crossref","unstructured":"Akash Kumar, C. Seshadhri, and Andrew Stolman. 2018. Finding Forbidden Minors in Sublinear Time: A O(n1\/2 + o(1))-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs. In Foundations of Computer Science (FOCS). 509&#8211;520.","DOI":"10.1109\/FOCS.2018.00055"},{"key":"key-10.1145\/3313276.3316330-16","doi-asserted-by":"crossref","unstructured":"Akash Kumar, C. Seshadhri, and Andrew Stolman. 2018. Finding forbidden minors in sublinear time: a O(n1\/2 + o(1))-query one-sided tester for minor closed properties on bounded degree graphs. CoRR abs\/1805.08187 (2018).","DOI":"10.1109\/FOCS.2018.00055"},{"key":"key-10.1145\/3313276.3316330-17","unstructured":"arXiv:1805.08187 http:\/\/arxiv.org\/abs\/1805.08187"},{"key":"key-10.1145\/3313276.3316330-18","unstructured":"K. Kuratowski. 1930. Sur le probl&#232;me des courbes gauches en topologie. Fundamenta Mathematica 15 (1930), 271&#8211;283."},{"key":"key-10.1145\/3313276.3316330-19","unstructured":"Reut Levi and Dana Ron. 2015. A quasi-polynomial time partition oracle for graphs with an excluded minor. ACM Transactions on Algorithms (TALG) 11, 3 (2015), 24."},{"key":"key-10.1145\/3313276.3316330-20","unstructured":"L&#225;szl&#243; Lov&#225;sz and Mikl&#243;s Simonovits. 1990. The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume. In Foundations of Computer Science (FOCS). 346&#8211;354."},{"key":"key-10.1145\/3313276.3316330-21","unstructured":"Ilan Newman and Christian Sohler. 2013. Every Property of Hyper&#983955;nite Graphs Is Testable. SIAM J. Comput. 42, 3 (2013), 1095&#8211;1112."},{"key":"key-10.1145\/3313276.3316330-22","unstructured":"N. Robertson and P. D. Seymour. 1995. Graph minors. XII. Distance on a surface. Journal of Combinatorial Theory Series B 64, 2 (1995), 240&#8211;272."},{"key":"key-10.1145\/3313276.3316330-23","unstructured":"N. Robertson and P. D. Seymour. 1995. Graph minors. XIII. The disjoint paths problem. Journal of Combinatorial Theory Series B 63, 1 (1995), 65&#8211;110."},{"key":"key-10.1145\/3313276.3316330-24","unstructured":"N. Robertson and P. D. Seymour. 2004. Graph minors. XX. Wagner&#8217;s conjecture. Journal of Combinatorial Theory Series B 92, 1 (2004), 325&#8211;357."},{"key":"key-10.1145\/3313276.3316330-25","unstructured":"D. Spielman. [n. d.]. Lecture notes on spectral graph theory. http:\/\/www.cs.yale.edu\/homes\/spielman\/eigs\/."},{"key":"key-10.1145\/3313276.3316330-26","unstructured":"D. Spielman and S.-H. Teng. 2012. A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning. SIAM J. Comput. 42, 1 (2012), 1&#8211;26."},{"key":"key-10.1145\/3313276.3316330-27","unstructured":"K. Wagner. 1937. &#220;ber eine eigenschaft der ebenen komplexe. Math. Ann. 114 (1937), 570&#8211;590."},{"key":"key-10.1145\/3313276.3316330-28","unstructured":"Yuichi Yoshida and Hiro Ito. 2015. Testing Outerplanarity of Bounded Degree Graphs. Algorithmica 73, 1 (2015), 1&#8211;20."}],"event":{"number":"2019","sponsor":["SIGACT, ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"STOC 2019","name":"the 51st Annual ACM SIGACT Symposium","start":{"date-parts":[[2019,6,23]]},"location":"Phoenix, AZ, USA","end":{"date-parts":[[2019,6,26]]}},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316330","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/dl.acm.org\/ft_gateway.cfm?id=3316330&ftid=2067716&dwn=1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:32Z","timestamp":1750204472000},"score":1,"resource":{"primary":{"URL":"http:\/\/dl.acm.org\/citation.cfm?doid=3313276.3316330"}},"subtitle":["a poly(<i>d \u03b5<\/i><sup>-1<\/sup>)-query tester for minor-closed properties of bounded degree graphs"],"proceedings-subject":"Theory of Computing","short-title":[],"issued":{"date-parts":[[2019]]},"references-count":29,"URL":"https:\/\/doi.org\/10.1145\/3313276.3316330","relation":{},"subject":[],"published":{"date-parts":[[2019]]}}}