Theses Doctoral

Lower Bounds and Explicit Constructions Through the Lens of Total Search Problems

Korten, Oliver

We cast the problem of proving strong circuit lower bounds, and more generally the problem of obtaining 𝘦𝘹𝘱𝘭π˜ͺ𝘀π˜ͺ𝘡 𝘀𝘰𝘯𝘴𝘡𝘳𝘢𝘀𝘡π˜ͺ𝘰𝘯𝘴 from probabilistic existence proofs, in the framework of total search problem complexity. Our analysis is centered around a total search problem called Range Avoidance: given a boolean circuit 𝐢 : {0,1}^𝑛 β†’ {0,1}^π‘š with π‘š > 𝑛, find 𝑦 ∈ {0,1}^π‘š which is not in the range of 𝐢.

Files

  • thumbnail for gsas-dissertations-000919.pdf gsas-dissertations-000919.pdf application/pdf 2.45 MB Download File

More About This Work

Academic Units
Computer Science
Thesis Advisors
Papadimitriou, Christos H.
Pitassi, Toniann
Degree
Ph.D., Columbia University
Published Here
October 28, 2026

Notes

Computational Complexity

Additional thesis advisor(s): Pitassi, Toniann