Explicit pseudorandom distributions for restricted models of computation

Kelley, Zander

Permalink

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

Description

Title

Explicit pseudorandom distributions for restricted models of computation

Author(s)

Kelley, Zander

Issue Date

2024-07-08

Director of Research (if dissertation) or Advisor (if thesis)

Forbes, Michael

Doctoral Committee Chair(s)

• Forbes, Michael
• Chekuri, Chandra

Committee Member(s)

• Erickson, Jeff G
• Meka, Raghu

Department of Study

Siebel Computing &DataScience

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• computational complexity
• pseudorandomness
• extremal combinatorics

Abstract

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

Graduation Semester

2024-08

Type of Resource

Thesis

Handle URL

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

Copyright and License Information

Copyright 2024 Zander Kelley

Owning Collections