{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:08:46Z","timestamp":1750306126427,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,8,17]],"date-time":"2017-08-17T00:00:00Z","timestamp":1502928000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["0645960"],"award-info":[{"award-number":["0645960"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2017,8,31]]},"abstract":"<jats:p>\n            We separate monotone analogues of\n            <jats:italic>L<\/jats:italic>\n            and\n            <jats:italic>NL<\/jats:italic>\n            by proving that any monotone switching network solving directed connectivity on\n            <jats:italic>n<\/jats:italic>\n            vertices must have size at least\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              \u03a9(lg\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            .\n          <\/jats:p>","DOI":"10.1145\/3080520","type":"journal-article","created":{"date-parts":[[2017,8,24]],"date-time":"2017-08-24T11:49:04Z","timestamp":1503575344000},"page":"1-48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Bounds on Monotone Switching Networks for Directed Connectivity"],"prefix":"10.1145","volume":"64","author":[{"given":"Aaron","family":"Potechin","sequence":"first","affiliation":[{"name":"Institute for Advanced Study"}]}],"member":"320","published-online":{"date-parts":[[2017,8,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.34"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579196"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218053"},{"key":"e_1_2_1_4_1","unstructured":"J. Brakensiek and A. Potechin. 2013. Bounds on the size of sound monotone switching networks accepting permutation sets of directed trees. arXiv 1301.3780.  J. Brakensiek and A. Potechin. 2013. Bounds on the size of sound monotone switching networks accepting permutation sets of directed trees. arXiv 1301.3780."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2014.v010a015"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209048"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795295948"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.70"},{"volume-title":"Proceedings of LMS Workshop on Boolean Function Complexity (M. S. Paterson, ed.)","author":"Gringi M.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796269"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217058"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62265"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1959.tb01585.x"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1996.0039"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11602613_77"},{"key":"e_1_2_1_16_1","unstructured":"W. Masek. 1976. A Fast Algorithm for the String Editing Problem and Decision Graph Complexity. Master\u2019s Thesis Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology.  W. Masek. 1976. A Fast Algorithm for the String Editing Problem and Decision Graph Complexity. Master\u2019s Thesis Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_2_1_18_1","unstructured":"A. Potechin. 2013. Improved upper and lower bound techniques for monotone switching networks for directed connectivity. arXiv 1302.3726.  A. Potechin. 2013. Improved upper and lower bound techniques for monotone switching networks for directed connectivity. arXiv 1302.3726."},{"volume-title":"Proceedings of the 38th Annual Symposium on Foundations of Computer Science. 234--243","author":"Raz R.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","first-page":"354","article-title":"Lower bounds for the monotone complexity of some boolean functions","volume":"31","author":"Razborov A.","year":"1985","journal-title":"Sov. Math. Dokl."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/647895.740448"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060647"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80006-X"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-AIEE.1938.5057767"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1949.tb03624.x"},{"key":"e_1_2_1_26_1","first-page":"96","article-title":"The method of forcing for nondeterministic automata","volume":"33","author":"Szelepcs\u00e9nyi R.","year":"1987","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060684"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3080520","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3080520","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3080520","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:58Z","timestamp":1750217818000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3080520"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,17]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,8,31]]}},"alternative-id":["10.1145\/3080520"],"URL":"https:\/\/doi.org\/10.1145\/3080520","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2017,8,17]]},"assertion":[{"value":"2011-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-08-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}