{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/125572"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/125572","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Explicit pseudorandom distributions for restricted models of computation","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-02-04 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-02-04 without embargo terms","abstract_has_math":false,"creators":["Kelley, Zander"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Forbes, Michael","Chekuri, Chandra","Erickson, Jeff G","Meka, Raghu"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2024,"date_issued":"2024-07-08","date_published":"2024-07-08","updated_at":"2026-07-22T22:25:02Z","subjects":["Computational Complexity","Pseudorandomness","Extremal Combinatorics"],"languages":["en","eng"],"rights":["Copyright 2024 Zander Kelley"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/125572","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Forbes, Michael","Chekuri, Chandra","Erickson, Jeff G","Meka, Raghu"]},{"key":"dc:creator","label":"Author","values":["Kelley, Zander"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2024-07-08","2024-08"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computational Complexity","Pseudorandomness","Extremal Combinatorics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2024 Zander Kelley"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/125572"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-02-04 without embargo terms","The student, Zander Kelley, accepted the attached license on 2024-07-05 at 13:13.","The student, Zander Kelley, submitted this Dissertation for approval on 2024-07-05 at 13:27.","This Dissertation was approved for publication on 2024-07-08 at 14:42.","DSpace SAF Submission Ingestion Package generated from Vireo submission #20960 on 2025-02-04 at 21:04:18","How can we understand the (provable) limitations of concrete models of computation? Answering this question is a necessary step for resolving the central unsolved problems of complexity theory, such as the \"P vs NP\" problem, and the \"P vs BPP\" problem. Many applications, such as cryptography, require more specifically a robust limitation, which is a computational task that bounded-complexity algorithms cannot even approximately perform. The topic of this thesis is pseudorandom distributions (for low-complexity models), which give a particularly clean way of exhibiting such limitations; a pseudorandom distribution is an (efficiently generated) random distribution over certain objects such that no low-complexity test function can reliably distinguish a typical example from a typical nonexample. This thesis is based on the pseudorandom distributions constructed and analyzed in our works [1, 2, 3, 4], each of which exhibits a robust limitation of one of the following particular computational models: - (Any-order) Read Once Branching Programs (a computational model capturing certain small space algorithms), - Constant-Depth Circuits (a computational model capturing certain highly parallelizable algorithms), - Polynomial Threshold Functions (a simple geometric model of computation that arises naturally e.g. in the context of learning theory), and - Multiparty Communication Protocols (an abstract model of computation useful for studying systems which are limited primarily by some communication bottleneck)."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Explicit pseudorandom distributions for restricted models of computation"]}]}],"canonical_facts":{"dc:contributor":["Forbes, Michael","Chekuri, Chandra","Erickson, Jeff G","Meka, Raghu"],"dc:creator":["Kelley, Zander"],"dc:date":["2024-07-08","2024-08"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-02-04 without embargo terms","The student, Zander Kelley, accepted the attached license on 2024-07-05 at 13:13.","The student, Zander Kelley, submitted this Dissertation for approval on 2024-07-05 at 13:27.","This Dissertation was approved for publication on 2024-07-08 at 14:42.","DSpace SAF Submission Ingestion Package generated from Vireo submission #20960 on 2025-02-04 at 21:04:18","How can we understand the (provable) limitations of concrete models of computation? Answering this question is a necessary step for resolving the central unsolved problems of complexity theory, such as the \"P vs NP\" problem, and the \"P vs BPP\" problem. Many applications, such as cryptography, require more specifically a robust limitation, which is a computational task that bounded-complexity algorithms cannot even approximately perform. The topic of this thesis is pseudorandom distributions (for low-complexity models), which give a particularly clean way of exhibiting such limitations; a pseudorandom distribution is an (efficiently generated) random distribution over certain objects such that no low-complexity test function can reliably distinguish a typical example from a typical nonexample. This thesis is based on the pseudorandom distributions constructed and analyzed in our works [1, 2, 3, 4], each of which exhibits a robust limitation of one of the following particular computational models: - (Any-order) Read Once Branching Programs (a computational model capturing certain small space algorithms), - Constant-Depth Circuits (a computational model capturing certain highly parallelizable algorithms), - Polynomial Threshold Functions (a simple geometric model of computation that arises naturally e.g. in the context of learning theory), and - Multiparty Communication Protocols (an abstract model of computation useful for studying systems which are limited primarily by some communication bottleneck)."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/125572"],"dc:language":["en","eng"],"dc:rights":["Copyright 2024 Zander Kelley"],"dc:subject":["Computational Complexity","Pseudorandomness","Extremal Combinatorics"],"dc:title":["Explicit pseudorandom distributions for restricted models of computation"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:02Z"}