2026-09-19T02:31:07Zhttps://ecommons.cornell.edu/server/oai/request

oai:ecommons.cornell.edu:1813/1172522026-05-15T19:51:57Zcom_1813_35col_1813_47

Liu, Yuhan Acharya, Jayadev Goldfeld, Ziv Sridharan, Karthik 2025-06-30T22:04:13Z 2025-06-30T22:04:13Z 2024-12 ProQuest Submission ID: 14665 ProQuest Publication ID: 31562052 https://hdl.handle.net/1813/117252 http://doi.org/10.7298/dfqg-s036 16921934 269 pages In modern data analysis, data may not always be fully accessible to analysts, potentially due to social concerns or physical restrictions. Since data may be costly to acquire, it is important to design data-efficient algorithms under information restrictions. This thesis establishes a general framework for proving the fundamental limit of information-constrained learning and designs sample-optimal algorithms under settings of practical interest. We consider various information constraints, including privacy and communication constraints on classical computers, and inherent randomness governed by the laws of physics in quantum computers. First, we study distribution learning and testing with local information constraints such as local differential privacy (LDP) and communication constraints. We derive a general lower-bound framework for interactive communication protocols. The techniques and ideas in this part lay the foundation for the quantum part. We then investigate user-level information constraints, a practical setup where each user or device may hold multiple samples. We design the first optimal algorithms for distribution estimation under central differential privacy. Finally, we demonstrate how prior ideas for classical problems surprisingly translate to the quantum world. Extending techniques for classical distribution testing, we propose a unified lower-bound framework for quantum state testing with restricted unentangled measurements. As a result, we derive the first known tight sample/copy complexity bounds for finite-outcome unentangled measurements and demonstrate the power of randomness in quantum state testing. en Attribution-ShareAlike 4.0 International https://creativecommons.org/licenses/by-sa/4.0/ Differential privacy Federated learning Information theory Quantum state testing Restricted measurements Statistical inference Learning with classical and quantum information constraints dissertation or thesis https://newcatalog.library.cornell.edu/catalog/16921934 application/pdf Electrical and Computer Engineering Cornell University Doctor of Philosophy Ph. D., Electrical and Computer Engineering https://hdl.handle.net/1813/59810.2 Publication Cornell Theses and Dissertations Liu, Yuhan 5893a6ea-7af3-41d7-abc6-04bcd26ab5df open.access open.access <Publication xmlns="https://www.openaire.eu/cerif-profile/1.1/" id="0869a485-62cf-4abd-9f1b-b8d7a9df167d"> <Type xmlns="https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types">http://purl.org/coar/resource_type/c_1843</Type> <Language>en</Language> <Title>Learning with classical and quantum information constraints</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2024-12</PublicationDate> <DOI>http://doi.org/10.7298/dfqg-s036</DOI> <Authors> <Author> <DisplayName>Liu, Yuhan</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <License>https://creativecommons.org/licenses/by-sa/4.0/</License> <Keyword>Differential privacy</Keyword> <Keyword>Federated learning</Keyword> <Keyword>Information theory</Keyword> <Keyword>Quantum state testing</Keyword> <Keyword>Restricted measurements</Keyword> <Keyword>Statistical inference</Keyword> <Abstract>In modern data analysis, data may not always be fully accessible to analysts, potentially due to social concerns or physical restrictions. Since data may be costly to acquire, it is important to design data-efficient algorithms under information restrictions. This thesis establishes a general framework for proving the fundamental limit of information-constrained learning and designs sample-optimal algorithms under settings of practical interest. We consider various information constraints, including privacy and communication constraints on classical computers, and inherent randomness governed by the laws of physics in quantum computers. First, we study distribution learning and testing with local information constraints such as local differential privacy (LDP) and communication constraints. We derive a general lower-bound framework for interactive communication protocols. The techniques and ideas in this part lay the foundation for the quantum part. We then investigate user-level information constraints, a practical setup where each user or device may hold multiple samples. We design the first optimal algorithms for distribution estimation under central differential privacy. Finally, we demonstrate how prior ideas for classical problems surprisingly translate to the quantum world. Extending techniques for classical distribution testing, we propose a unified lower-bound framework for quantum state testing with restricted unentangled measurements. As a result, we derive the first known tight sample/copy complexity bounds for finite-outcome unentangled measurements and demonstrate the power of randomness in quantum state testing.</Abstract> <Access xmlns="http://purl.org/coar/access_right" > </Access> </Publication>