Finite Playground

To verify is human; to prove, divine.

MA-SETH is false

Leave a comment

Ryan Williams just posted a new paper Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation on ECCC, in which he disproves the MA analog of the Strong Exponential Time Hypothesis (MA-SETH), which is motivated by the paper Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility by Carmosino, Gao, Impagliazzo, Mikhailin, Paturi, and Schneider, proving that assuming Nondeterministic Strong Exponential Time Hypothesis (NSETH) then some problems like 3SUM and APSP cannot be SETH-hard.

 

Author: hcsoso

Ph.D. student in the Department of Computer Science, University of Illinois at Urbana-Champaign.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s