All reports by Author Neekon Vafa:

__
TR24-014
| 28th January 2024
__

Elette Boyle, Ilan Komargodski, Neekon Vafa#### Memory Checking Requires Logarithmic Overhead

__
TR21-166
| 21st November 2021
__

Lijie Chen, Shuichi Hirahara, Neekon Vafa#### Average-case Hardness of NP and PH from Worst-case Fine-grained Assumptions

__
TR18-173
| 17th October 2018
__

Eric Allender, Rahul Ilango, Neekon Vafa#### The Non-Hardness of Approximating Circuit Size

Revisions: 1

Elette Boyle, Ilan Komargodski, Neekon Vafa

We study the complexity of memory checkers with computational security and prove the first general tight lower bound.

Memory checkers, first introduced over 30 years ago by Blum, Evans, Gemmel, Kannan, and Naor (FOCS '91, Algorithmica '94), allow a user to store and maintain a large memory on a remote ... more >>>

Lijie Chen, Shuichi Hirahara, Neekon Vafa

What is a minimal worst-case complexity assumption that implies non-trivial average-case hardness of NP or PH? This question is well motivated by the theory of fine-grained average-case complexity and fine-grained cryptography. In this paper, we show that several standard worst-case complexity assumptions are sufficient to imply non-trivial average-case hardness ... more >>>

Eric Allender, Rahul Ilango, Neekon Vafa

The Minimum Circuit Size Problem (MCSP) has been the focus of intense study recently; MCSP is hard for SZK under rather powerful reductions, and is provably not hard under “local” reductions computable in TIME($n^{0.49}$). The question of whether MCSP is NP-hard (or indeed, hard even for small subclasses of P) ... more >>>