The complexity of explicit construction problems

Thesis

Explicit constructions of pseudorandom objects play a central role in theoretical computer science. Unfortunately, for many properties of interest, while a randomly chosen object would satisfy them with high probability, deterministically constructing such objects remains notoriously challenging. For example, Erdős famously showed that a random graph is almost always a Ramsey graph, yet explicitly constructing Ramsey graphs has been a long-standing open problem.

Recently, ...

Expand abstract

Authors: Ren, H

• DOI: 10.5287/ora-eonz7e2qn
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: circuit complexity; range avoidance; explicit construction
• Subjects: Computational complexity