Better Hardness via Algorithms, and New Forms of Hardness versus Randomness
One central theme of complexity theory is the rich interplay between hardness (the existence of functions that are hard to compute) and pseudorandomness (the procedure that converts randomized algorithms into equivalent deterministic algorithms). In one direction, from the classic works of Nisan-Wid...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2023
|
| Online Access: | https://hdl.handle.net/1721.1/147560 |