Malvika Raj Joshi

Malvika Raj Joshi

Scholar Title

MIT EECS | Fano Undergraduate Research and Innovation Scholar

Research Title

Nondeterministic SETH: Short Unsatisfiability Proofs for Boolean Formulas

Cohort

2019–2020

Department

EECS

Research Areas
  • Theory of Computer Systems
Supervisor

Ryan Williams

Abstract

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

Quote

“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.”

Back to Scholars