The strong exponential time hypothesis (SETH) is one of the most important unresolved hardness assumptions in theoretical computer science. It is a much stronger assumption than P != NP and says that k-SAT cannot be solved in O(1.999^n) time. There are analogs of SETH for the complexity class NP and MA. NSETH (Nondeterminisitc SETH), claims that there are no proofs of size less than O(1.999^n) for k-UNSAT. The randomized version of this, MASETH, was disproved in 2016 by Prof. Ryan 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.