Research Project Title:
abstract:The strong exponential time hypothesis (SETH) is one of the most important unresolved problems in theoretical computer science. It says that for every Îµ > 0, there is a k such that k-SAT cannot be solved in O(2^(1âˆ’Îµ)n) time. There are analogs of SETH for the complexity class NP and MA. NSETH (Nondeterminisitc SETH), claims that for every Îµ > 0, there is a k such that k-UNSAT cannot be solved in O(2^(1âˆ’Îµ)n) nondeterministic time. The randomized version of this, MASETH, was disproved in 2016 by Williams, who showed that there is a fast MA protocol for evaluating an arithmetic circuit on multiple inputs and used this to give a protocol for UNSAT. The goal of this project is to study NSETH and attempt to derandomize the MA protocol for UNSAT to disprove it.
"I got interested in NSETH when I learned about SETH and its related problems in a class taught by Professors Ryan Williams and Virginia Williams on fine-grained algorithms and complexity. I am excited to apply the techniques I have learnt in this class and in other theoretical computer science classes to this problem. I hope to develop a deeper understanding of the hypothesized lower bounds and their implications and contribute to the field."