Resource type
Thesis type
(Thesis) Ph.D.
Date created
2026-07-20
Authors/Contributors
Author: Goldberg, Halley
Abstract
The goal of this work is to explore connections between meta-complexity and fundamental questions of average-case complexity theory and learning theory. In particular, we aim to make concrete progress on the latter by application of meta-complexity as a tool. The contributions of the thesis fall along two threads. In the first, we apply techniques from meta-complexity to shed light on the computational nature of our world. This line of research ultimately aims to base the possibility of cryptography on the hardness of NP. Among other contributions, we establish the following: (1a) a worst-case to average-case reduction for randomized algorithms, which proceeds by introduction of a new complexity measure purpose-built for the study of probabilistic computation; (2a) an equivalence between NP-hardness of learning and the existence of Witness Encryption (Garg et al., STOC'13); (3a) a proof that under assumptions of NP-hardness of time-bounded Kolmogorov complexity, the existence of one-way functions follows from the worst-case hardness of NP, and the polynomial-time hierarchy collapses. In the second thread, we work to situate the complexity of computational learning within the broader landscape of complexity theory. To that end, we establish the following: (1b) agnostic PAC learning algorithms working from random examples, assuming average-case easiness of time-bounded Kolmogorov complexity; (2b) several unconditional NP-hardness results for learning---for example, 'semi-proper' PAC learning of general boolean circuits is NP-hard, and improper learning of random-access machines is NP-hard; (3b) a proof that Implicit MCSP and learning over full-support distributions are NP-hard under provably non-Levin many-one reductions, assuming the existence of Indistinguishability Obfuscation and the non-existence of optimal Cook-Reckhow proof systems. In all cases, we work to paint a clearer picture of the web of connections between meta-complexity, learning theory, and the topics at stake in Impagliazzo's 'five worlds' (Impagliazzo, SCT'95).
File
Extent
243 pages.
Identifier
etd24417
Copyright statement
Copyright is held by the author(s).
Academic Supervisor
Thesis advisor: Kabanets, Valentine
Language
English
Member of collection
| Download file | Size |
|---|---|
| etd24417.pdf | 1.39 MB |