{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:04:37Z","timestamp":1750309477810,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":43,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["OMA-2016245,CCF-1714779,CCF-2007462"],"award-info":[{"award-number":["OMA-2016245,CCF-1714779,CCF-2007462"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100017637","name":"Simons Institute for the Theory of Computing, University of California Berkeley","doi-asserted-by":"publisher","award":["HR00112020023"],"award-info":[{"award-number":["HR00112020023"]}],"id":[{"id":"10.13039\/100017637","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585129","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"1097-1110","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory"],"prefix":"10.1145","author":[{"given":"Qipeng","family":"Liu","sequence":"first","affiliation":[{"name":"Simons Institute for the Theory of Computing, Berkeley, USA"}]},{"given":"Ran","family":"Raz","sequence":"additional","affiliation":[{"name":"Princeton University, USA"}]},{"given":"Wei","family":"Zhan","sequence":"additional","affiliation":[{"name":"Princeton University, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M120275X"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-021-27922-0"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-019-1666-5"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2002.1003845"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48405-1_5"},{"key":"e_1_3_2_1_6_1","volume-title":"Conference On Learning Theory, COLT 2018","author":"Beame Paul","year":"2018","unstructured":"Paul Beame , Shayan Oveis Gharan , and Xin Yang . 2018 . Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials . In Conference On Learning Theory, COLT 2018 , Stockholm, Sweden , 6-9 July 2018, S\u00e9bastien Bubeck, Vianney Perchet, and Philippe Rigollet (Eds.) (Proceedings of Machine Learning Research, Vol. 75). PMLR, 843\u2013856. Paul Beame, Shayan Oveis Gharan, and Xin Yang. 2018. Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials. In Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, S\u00e9bastien Bubeck, Vianney Perchet, and Philippe Rigollet (Eds.) (Proceedings of Machine Learning Research, Vol. 75). PMLR, 843\u2013856."},{"key":"e_1_3_2_1_7_1","unstructured":"Anne Broadbent and Peter Yuen. 2021. Device-Independent Oblivious Transfer from the Bounded-Quantum-Storage-Model and Computational Assumptions. arxiv:2111.08595. \t\t\t\t  Anne Broadbent and Peter Yuen. 2021. Device-Independent Oblivious Transfer from the Bounded-Quantum-Storage-Model and Computational Assumptions. arxiv:2111.08595."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00070"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0052243"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4310\/mrl.2001.v8.n3.a1"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00063"},{"key":"e_1_3_2_1_12_1","volume-title":"Toward Instance-Optimal State Certification With Incoherent Measurements. In Conference on Learning Theory","volume":"2596","author":"Chen Sitan","year":"2022","unstructured":"Sitan Chen , Jerry Li , and Ryan O\u2019Donnell . 2022 . Toward Instance-Optimal State Certification With Incoherent Measurements. In Conference on Learning Theory , 2-5 July 2022, London, UK, Po-Ling Loh and Maxim Raginsky (Eds.) (Proceedings of Machine Learning Research , Vol. 178). PMLR, 2541\u2013 2596 . Sitan Chen, Jerry Li, and Ryan O\u2019Donnell. 2022. Toward Instance-Optimal State Certification With Incoherent Measurements. In Conference on Learning Theory, 2-5 July 2022, London, UK, Po-Ling Loh and Maxim Raginsky (Eds.) (Proceedings of Machine Learning Research, Vol. 178). PMLR, 2541\u20132596."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74143-5_20"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/060651343"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.09.014"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45841-7_1"},{"key":"e_1_3_2_1_17_1","volume-title":"Speak Much","author":"Dodis Yevgeniy","year":"2021","unstructured":"Yevgeniy Dodis , Willy Quach , and Daniel Wichs . 2021. Speak Much , Remember Little : Cryptography in the Bounded Storage Model, Revisited. Cryptology ePrint Archive, Paper 2021 \/1270. https:\/\/eprint.iacr.org\/2021\/1270 Yevgeniy Dodis, Willy Quach, and Daniel Wichs. 2021. Speak Much, Remember Little: Cryptography in the Bounded Storage Model, Revisited. Cryptology ePrint Archive, Paper 2021\/1270. https:\/\/eprint.iacr.org\/2021\/1270"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-07082-2_26"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509960"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24676-3_8"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2021.60"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2020.21"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188962"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/070706550"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17659-4_17"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2719044"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/11787006_17"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41567-020-0932-7"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055430"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-92641-0_14"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45708-9_17"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00191321"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-008-9035-9"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2018.28"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevX.3.031007"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.73"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186563"},{"key":"e_1_3_2_1_38_1","unstructured":"Christian Schaffner. 2007. Cryptography in the Bounded-Quantum-Storage Model. arxiv:0709.0289. \t\t\t\t  Christian Schaffner. 2007. Cryptography in the Bounded-Quantum-Storage Model. arxiv:0709.0289."},{"key":"e_1_3_2_1_39_1","volume-title":"Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems","author":"Shamir Ohad","year":"2014","unstructured":"Ohad Shamir . 2014. Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation . In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014 , December 8-13 2014, Montreal, Quebec, Canada, Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger (Eds .). 163\u2013171. Ohad Shamir. 2014. Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger (Eds.). 163\u2013171."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316403"},{"key":"e_1_3_2_1_41_1","volume-title":"Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir (Eds.) (JMLR Workshop and Conference Proceedings","volume":"1516","author":"Steinhardt Jacob","year":"2016","unstructured":"Jacob Steinhardt , Gregory Valiant , and Stefan Wager . 2016 . Memory, Communication, and Statistical Queries . In Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir (Eds.) (JMLR Workshop and Conference Proceedings , Vol. 49). JMLR.org, 1490\u2013 1516 . Jacob Steinhardt, Gregory Valiant, and Stefan Wager. 2016. Memory, Communication, and Statistical Queries. In Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir (Eds.) (JMLR Workshop and Conference Proceedings, Vol. 49). JMLR.org, 1490\u20131516."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_49"},{"volume-title":"How to learn a quantum state. Ph. D. Dissertation","author":"Wright John","key":"e_1_3_2_1_43_1","unstructured":"John Wright . 2016. How to learn a quantum state. Ph. D. Dissertation . Carnegie Mellon University . John Wright. 2016. How to learn a quantum state. Ph. D. Dissertation. Carnegie Mellon University."}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Orlando FL USA","acronym":"STOC '23"},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585129","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585129","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585129","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:27Z","timestamp":1750295847000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585129"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":43,"alternative-id":["10.1145\/3564246.3585129","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585129","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}