{"id":{"repo_id":"cornell","oai_identifier":"oai:ecommons.cornell.edu:1813/117252"},"canonical_url":"https://search.dev.ndltd.org/etd/cornell/oai:ecommons.cornell.edu:1813/117252","repository":{"repo_id":"cornell","name":"Cornell University","base_url":"https://ecommons.cornell.edu/server/oai/request"},"display":{"title":"Learning with classical and quantum information constraints","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_html":"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_has_math":false,"creators":["Liu, Yuhan"],"institution":"Cornell University","degree_name":"Ph. D., Electrical and Computer Engineering","degree_level":"Doctor of Philosophy","degree_discipline":"Electrical and Computer Engineering","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":["Goldfeld, Ziv","Sridharan, Karthik"],"year":2024,"date_issued":"2024-12","date_published":"2024-12","updated_at":"2026-07-24T01:49:04Z","subjects":["Differential privacy","Federated learning","Information theory","Quantum state testing","Restricted measurements","Statistical inference"],"languages":["en"],"rights":["Attribution-ShareAlike 4.0 International"],"rights_urls":["https://creativecommons.org/licenses/by-sa/4.0/"],"identifier_entries":[{"key":"dc:identifier.doi","label":"DOI","values":["http://doi.org/10.7298/dfqg-s036"],"render_values":[{"text":"http://doi.org/10.7298/dfqg-s036","href":"http://doi.org/10.7298/dfqg-s036","code":true}]},{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["ProQuest Submission ID: 14665","ProQuest Publication ID: 31562052"],"render_values":[{"text":"ProQuest Submission ID: 14665","href":null,"code":true},{"text":"ProQuest Publication ID: 31562052","href":null,"code":true}]}]},"links":{"outbound_url":"https://hdl.handle.net/1813/117252","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Goldfeld, Ziv","Sridharan, Karthik"]},{"key":"dc:creator","label":"Author","values":["Liu, Yuhan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2025-06-30T22:04:13Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2025-06-30T22:04:13Z"]},{"key":"dc:date.issued","label":"Date","values":["2024-12"]},{"key":"dc:type","label":"Dc Type","values":["dissertation or thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical and Computer Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Doctor of Philosophy"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph. D., Electrical and Computer Engineering"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Cornell University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Differential privacy","Federated learning","Information theory","Quantum state testing","Restricted measurements","Statistical inference"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Attribution-ShareAlike 4.0 International"]},{"key":"dc:rights.uri","label":"Rights URI","values":["https://creativecommons.org/licenses/by-sa/4.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.doi","label":"DOI","values":["http://doi.org/10.7298/dfqg-s036"]},{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["ProQuest Submission ID: 14665","ProQuest Publication ID: 31562052"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1813/117252"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["269 pages"]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Learning with classical and quantum information constraints"]}]}],"canonical_facts":{"dc:contributor.committeemember":["Goldfeld, Ziv","Sridharan, Karthik"],"dc:creator":["Liu, Yuhan"],"dc:date.accessioned":["2025-06-30T22:04:13Z"],"dc:date.available":["2025-06-30T22:04:13Z"],"dc:date.issued":["2024-12"],"dc:description":["269 pages"],"dc:description.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."],"dc:format.mimetype":["application/pdf"],"dc:identifier.doi":["http://doi.org/10.7298/dfqg-s036"],"dc:identifier.other":["ProQuest Submission ID: 14665","ProQuest Publication ID: 31562052"],"dc:identifier.uri":["https://hdl.handle.net/1813/117252"],"dc:language.iso":["en"],"dc:rights":["Attribution-ShareAlike 4.0 International"],"dc:rights.uri":["https://creativecommons.org/licenses/by-sa/4.0/"],"dc:subject":["Differential privacy","Federated learning","Information theory","Quantum state testing","Restricted measurements","Statistical inference"],"dc:title":["Learning with classical and quantum information constraints"],"dc:type":["dissertation or thesis"],"thesis:degree_discipline":["Electrical and Computer Engineering"],"thesis:degree_level":["Doctor of Philosophy"],"thesis:degree_name":["Ph. D., Electrical and Computer Engineering"],"thesis:institution_name":["Cornell University"]},"updated_at":"2026-07-24T01:49:04Z"}