{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:02Z","timestamp":1781031422982,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":80,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"JST ACT-X","award":["JPMJAX24CJ"],"award-info":[{"award-number":["JPMJAX24CJ"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800755","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"354-364","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Sharp Characterization of Pessiland"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3101-446X","authenticated-orcid":false,"given":"Shuichi","family":"Hirahara","sequence":"first","affiliation":[{"name":"National Institute of Informatics, Tokyo, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-4064-1462","authenticated-orcid":false,"given":"Mikito","family":"Nanashima","sequence":"additional","affiliation":[{"name":"Institute of Science Tokyo, Tokyo, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585227"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132614"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.04.011"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.2307\/2694916"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/06066850X"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2021.7"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.35"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-84252-9_21"},{"key":"e_1_3_2_1_9_1","volume-title":"Computational Complexity - A Modern Approach","author":"Arora Sanjeev","unstructured":"Sanjeev Arora and Boaz Barak. 2009. Computational Complexity - A Modern Approach. Cambridge University Press. isbn:978-0-521-42426-4"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-34799-2_3"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3586165.3586172"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48329-2_24"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46494-6_1"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000004"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446974"},{"key":"e_1_3_2_1_16_1","volume-title":"Proceedings of the Symposium on Discrete Algorithms (SODA). 345\u2013353","author":"Carr Robert D.","unstructured":"Robert D. Carr, Srinivas Doddi, Goran Konjevod, and Madhav V. Marathe. 2000. On the red-blue set cover problem. In Proceedings of the Symposium on Discrete Algorithms (SODA). 345\u2013353."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.APPROX-RANDOM.2016.4"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384283"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897520"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591820"},{"key":"e_1_3_2_1_21_1","volume-title":"Proceedings of the Conference on Learning Theory (COLT). 815\u2013830","author":"Daniely Amit","year":"2016","unstructured":"Amit Daniely and Shai Shalev-Shwartz. 2016. Complexity Theoretic Limitations on Learning DNF\u2019s. In Proceedings of the Conference on Learning Theory (COLT). 815\u2013830."},{"key":"e_1_3_2_1_22_1","volume-title":"Proceedings of the Conference on Learning Theory (COLT). 1358\u20131394","author":"Daniely Amit","year":"2021","unstructured":"Amit Daniely and Gal Vardi. 2021. From Local Pseudorandom Generators to Hardness of Learning. In Proceedings of the Conference on Learning Theory (COLT). 1358\u20131394."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0014-4"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746630"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2003.11.007"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222061"},{"key":"e_1_3_2_1_27_1","volume-title":"Innovations in Computer Science - ICS","author":"Feldman Vitaly","year":"2010","unstructured":"Vitaly Feldman. 2010. Distribution-Specific Agnostic Boosting. In Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 5-7, 2010. Proceedings. 241\u2013250."},{"key":"e_1_3_2_1_28_1","volume-title":"Boosting: Foundations and Algorithms. Adaptive computation and machine learning","author":"Freund Yoav","year":"2012","unstructured":"Yoav Freund and Robert E Schapire. 2012. Boosting: Foundations and Algorithms. Adaptive computation and machine learning. MIT Press, 2 (2012), 8."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520072"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2023.12"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/6490.6503"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116852"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-63307-3_70"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90070-9"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00095"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585130"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585138"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00030"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00078"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00033"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649701"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2017.7"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00048"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520051"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1995.514853"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.34"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89604"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63483"},{"key":"e_1_3_2_1_51_1","volume-title":"Potential-Based Agnostic Boosting. In Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of a meeting held","author":"Kalai Adam","year":"2009","unstructured":"Adam Kalai and Varun Kanade. 2009. Potential-Based Agnostic Boosting. In Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of a meeting held 7-10 December 2009, Vancouver, British Columbia, Canada. 880\u2013888."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_67"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220059"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00118"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-84242-0_2"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2022.36"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-48615-9_8"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-38545-2_21"},{"key":"e_1_3_2_1_60_1","volume-title":"Innovations in Computer Science - ICS","author":"Livne Noam","year":"2010","unstructured":"Noam Livne. 2010. On the Construction of One-Way Functions from Average Case Hardness. In Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 5-7, 2010. Proceedings. 301\u2013309."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2024.110"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/1754399.1754402"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-010-0047-x"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2021.29"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00196774"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143926"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.71"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISTCS.1993.253489"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000074"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2012.43"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2021.35"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116037"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(64)90223-2"},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0233-x"},{"key":"e_1_3_2_1_76_1","volume-title":"Refutation. In Proceedings of the Conference on Learning Theory (COLT). 1835\u20131848","author":"Vadhan Salil P.","year":"2017","unstructured":"Salil P. Vadhan. 2017. On Learning vs. Refutation. In Proceedings of the Conference on Learning Theory (COLT). 1835\u20131848."},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2005.16"},{"key":"e_1_3_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/2355580.2355583"},{"key":"e_1_3_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_22"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800755","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:59:42Z","timestamp":1781027982000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800755"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":80,"alternative-id":["10.1145\/3798129.3800755","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800755","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}