SCS Undergraduate Thesis Topics
|David Charlton||Manuel Blum||On the Hardness of Uniform Random Generation|
The ability to randomly generate combinatorial objects is the fundamental technique underlying cryptography. The ability to randomly generate distributions of "hard" problems is useful for encryption and security. In addition, algorithms to randomly generate certain structures can teach us more about the structures themselves: some properties of regular graphs have been discovered by analyzing algorithms known to randomly generate them.
Despite this, there has been little general research into random generation algorithms. For example, it is unknown whether there is an efficient algorithm that will uniformly generate an NP-complete language.
My thesis aims to study the questions: In general, how computationally difficult is it to randomly generate a distribution? Can any NP-complete problems be efficiently generated? And, how does the computational intractibility of a particular problem affect the difficulty of randomly generating instances of that problem?