Explicit pseudorandom distributions for restricted models of computation

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).

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2024

Author dc:creator

• Kelley, Zander

Contributors dc:contributor

• Forbes, Michael
• Chekuri, Chandra
• Erickson, Jeff G
• Meka, Raghu

• Computational Complexity
• Pseudorandomness
• Extremal Combinatorics

Statement dc:rights

• Copyright 2024 Zander Kelley

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/125572

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F125572