2026 Theses Doctoral
Lower Bounds and Explicit Constructions Through the Lens of Total Search Problems
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
-
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