{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:56:54Z","timestamp":1781031414045,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":43,"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":"Swiss State Secretariat for Education, Research and Innovation (SERI)","award":["MB22.00026"],"award-info":[{"award-number":["MB22.00026"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800743","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"234-245","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Sampling Permutations with Cell Probes Is Hard"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3196-6919","authenticated-orcid":false,"given":"Yaroslav","family":"Alekseev","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-5095-7382","authenticated-orcid":false,"given":"Mika","family":"G\u00f6\u00f6s","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-5849-8337","authenticated-orcid":false,"given":"Konstantin","family":"Myasnikov","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-8393-812X","authenticated-orcid":false,"given":"Artur","family":"Riazanov","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2809-3467","authenticated-orcid":false,"given":"Dmitry","family":"Sokolov","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"},{"name":"Universit\u00e9 de Montr\u00e9al, Montr\u00e9al, Canada"}],"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.1016\/0020-0190(87)90036-6"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.82"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2022.40"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897528"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(86)90019-1"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.27"},{"key":"e_1_3_2_1_7_1","volume-title":"An extension of McDiarmid\u2019s inequality. CoRR, abs\/1511.05240","author":"Combes Richard","year":"2015","unstructured":"Richard Combes. 2015. An extension of McDiarmid\u2019s inequality. CoRR, abs\/1511.05240 (2015), arXiv:1511.05240."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746629"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<238::AID-RSA4>3.0.CO;2-E"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/364520.364540"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.APPROX\/RANDOM.2023.36"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.69"},{"key":"e_1_3_2_1_14_1","unstructured":"Daniel Grier Daniel M. Kane Jackson Morris Anthony Ostuni and Kewen Wu. 2025. Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals. arxiv:2510.07808."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-54233-7_151"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(66)80059-5"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649670"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718243"},{"key":"e_1_3_2_1_19_1","unstructured":"Daniel M. Kane Anthony Ostuni and Kewen Wu. 2025. Symmetric Distributions from Shallow Circuits. https:\/\/eccc.weizmann.ac.il\/report\/2025\/183\/"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0039-3"},{"key":"e_1_3_2_1_21_1","volume-title":"Extension of the law of large numbers to quantities, depending on each other","author":"Markov A.A.","year":"1906","unstructured":"A.A. Markov. 2006. Extension of the law of large numbers to quantities, depending on each other (1906). Reprint.. Journal \u00c9lectronique d\u2019Histoire des Probabilit\u00e9s et de la Statistique [electronic only], 2, 1b (2006), Article 10, 12 p., electronic only\u2013Article 10, 12 p., electronic only."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103453"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107359949.008"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","unstructured":"Ravi Montenegro and Prasad Tetali. 2006. Mathematical Aspects of Mixing Times in Markov Chains. https:\/\/doi.org\/10.1561\/0400000003 10.1561\/0400000003","DOI":"10.1561\/0400000003"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/050636231"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1214\/08-AOP409"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000478"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03356-8_17"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.03.005"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.9"},{"key":"e_1_3_2_1_31_1","volume-title":"Principles of Mathematical Analysis","author":"Rudin W.","unstructured":"W. Rudin. 1976. Principles of Mathematical Analysis. McGraw-Hill. isbn:9780070856134 lccn:75179033"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649735"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.2307\/2284510"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/090766619"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/100814998"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/11085983X"},{"key":"e_1_3_2_1_37_1","unstructured":"Emanuelle Viola. 2018. The Complexity of Distributions. https:\/\/www.youtube.com\/live\/O78b085HE3w?si=i7e44r9QuNzrR2dV&t=324 Talk at Simons Institute"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1198405"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2023.26"},{"key":"e_1_3_2_1_40_1","unstructured":"Adam Bene Watts and Natalie Parham. 2023. Unconditional Quantum Advantage for Sampling with Shallow Circuits. arxiv:2301.00995."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/322261.322274"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384274"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2024.100"}],"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.3800743","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:58:30Z","timestamp":1781027910000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800743"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":43,"alternative-id":["10.1145\/3798129.3800743","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800743","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"}}]}}