Malvika Raj Joshi

Malvika Raj Joshi
MIT EECS | Fano Undergraduate Research and Innovation Scholar
Advisor: Ryan Williams
Department: EECS
Areas of Research: Theory of Computer Systems
Years: 2019-2020
Research Project Title:

Nondeterministic SETH

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."