{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:58Z","timestamp":1750220638935,"version":"3.41.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,11,8]],"date-time":"2020-11-08T00:00:00Z","timestamp":1604793600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1657377"],"award-info":[{"award-number":["CCF-1657377"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2020,12,31]]},"abstract":"<jats:p>\n            The complexity class ZPP\n            <jats:sup>NP[1]<\/jats:sup>\n            (corresponding to zero-error randomized algorithms with access to one NP oracle query) is known to have a number of curious properties. We further explore this class in the settings of time complexity, query complexity, and communication complexity.\n          <\/jats:p>\n          <jats:p>\n            \u2022 For starters, we provide a new characterization: ZPP\n            <jats:sup>NP[1]<\/jats:sup>\n            <jats:italic>equals<\/jats:italic>\n            the restriction of BPP\n            <jats:sup>NP[1]<\/jats:sup>\n            where the algorithm is only allowed to err when it forgoes the opportunity to make an NP oracle query.\n          <\/jats:p>\n          <jats:p>\n            \u2022 Using the above characterization, we prove a\n            <jats:italic>query-to-communication lifting theorem<\/jats:italic>\n            , which translates any ZPP\n            <jats:sup>NP[1]<\/jats:sup>\n            decision tree lower bound for a function\n            <jats:italic>f<\/jats:italic>\n            into a ZPP\n            <jats:sup>NP[1]<\/jats:sup>\n            communication lower bound for a two-party version of\n            <jats:italic>f<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            \u2022 As an application, we use the above lifting theorem to prove that the ZPP\n            <jats:sup>NP[1]<\/jats:sup>\n            communication lower bound technique introduced by G\u00f6\u00f6s, Pitassi, and Watson (ICALP 2016) is not tight. We also provide a \u201cprimal\u201d characterization of this lower bound technique as a complexity class.\n          <\/jats:p>","DOI":"10.1145\/3428673","type":"journal-article","created":{"date-parts":[[2020,11,8]],"date-time":"2020-11-08T11:52:50Z","timestamp":1604836370000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["A ZPP\n            <sup>NP[1]<\/sup>\n            Lifting Theorem"],"prefix":"10.1145","volume":"12","author":[{"given":"Thomas","family":"Watson","sequence":"first","affiliation":[{"name":"University of Memphis, TN"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,11,8]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1137\/15M1050902"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/2897518.2897644"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.5555\/2982445.2982449"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1109\/FOCS.2016.66"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1145\/3055399.3055407"},{"volume-title":"Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS\u201917)","year":"2017","author":"Ben-David Shalev","key":"e_1_2_1_6_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1137\/S0097539799352474"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1109\/FOCS.2017.71"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1016\/S0304-3975(01)00144-X"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1109\/CCC.2007.18"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1007\/s10878-006-7130-0"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1145\/2811255"},{"volume-title":"Proceedings of the 23rd Conference on Computational Complexity (CCC\u201908)","year":"2008","author":"Chang Richard","key":"e_1_2_1_13_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1145\/3188745.3188874"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1007\/s00037-019-00190-7"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1109\/FOCS.2016.40"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1145\/3188745.3188838"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1109\/FOCS.2015.69"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1145\/3170711"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1007\/s00037-018-0175-5"},{"volume-title":"Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS\u201919)","year":"2019","author":"G\u00f6\u00f6s Mika","key":"e_1_2_1_21_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1137\/15M103145X"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1137\/16M1082007"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1109\/FOCS.2017.21"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1137\/16M1059369"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1007\/s00037-018-0166-6"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1109\/FOCS.2018.00045"},{"key":"e_1_2_1_28_1","first-page":"1","article-title":"Communication complexity of set-disjointness for all probabilities","volume":"12","author":"G\u00f6\u00f6s Mika","year":"2016","journal-title":"Theory Comput."},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1016\/0022-0000(90)90027-I"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1109\/CCC.2010.32"},{"volume-title":"Depth lower bounds for monotone semi-unbounded fan-in circuits. RAIRO\u2014Theoret. Info. Appl. 35","year":"2001","author":"Johannsen Jan","key":"e_1_2_1_31_1"},{"volume-title":"Boolean Function Complexity: Advances and Frontiers. Algorithms and Combinatorics","author":"Jukna Stasys","key":"e_1_2_1_32_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1109\/CCC.2003.1214415"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.5555\/1328722.1328729"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1109\/CCC.2011.33"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1145\/3055399.3055438"},{"volume-title":"Communication Complexity","author":"Kushilevitz Eyal","key":"e_1_2_1_37_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_1","DOI":"10.1145\/2746539.2746599"},{"doi-asserted-by":"publisher","key":"e_1_2_1_39_1","DOI":"10.1016\/0020-0190(91)90157-D"},{"doi-asserted-by":"publisher","key":"e_1_2_1_40_1","DOI":"10.1145\/3196832"},{"doi-asserted-by":"publisher","key":"e_1_2_1_41_1","DOI":"10.1109\/CCC.2014.37"},{"doi-asserted-by":"publisher","key":"e_1_2_1_42_1","DOI":"10.1145\/3055399.3055478"},{"doi-asserted-by":"publisher","key":"e_1_2_1_43_1","DOI":"10.1145\/3188745.3188914"},{"key":"e_1_2_1_44_1","first-page":"1","article-title":"Nondeterministic and randomized Boolean hierarchies in communication complexity. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP\u201920)","volume":"92","author":"Pitassi Toniann","year":"2020","journal-title":"Schloss Dagstuhl"},{"volume-title":"Communication Complexity and Applications","author":"Rao Anup","key":"e_1_2_1_45_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_46_1","DOI":"10.5555\/795663.796321"},{"doi-asserted-by":"publisher","key":"e_1_2_1_47_1","DOI":"10.1109\/FOCS.2016.51"},{"doi-asserted-by":"publisher","key":"e_1_2_1_48_1","DOI":"10.1109\/FOCS.2016.32"},{"doi-asserted-by":"publisher","key":"e_1_2_1_49_1","DOI":"10.1137\/080733644"},{"doi-asserted-by":"publisher","key":"e_1_2_1_50_1","DOI":"10.1007\/s00224-008-9126-x"},{"volume-title":"Provability, Complexity, Grammars. AMS Translations","author":"Vereshchagin Nikolai","series-title":"Series 2","key":"e_1_2_1_51_1"},{"key":"e_1_2_1_52_1","first-page":"1","article-title":"Amplification with one NP oracle query. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP\u201919)","volume":"96","author":"Watson Thomas","year":"2019","journal-title":"Track A. Schloss Dagstuhl"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428673","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3428673","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3428673","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:59Z","timestamp":1750197719000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428673"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,8]]},"references-count":52,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,12,31]]}},"alternative-id":["10.1145\/3428673"],"URL":"https:\/\/doi.org\/10.1145\/3428673","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2020,11,8]]},"assertion":[{"value":"2018-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-11-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}