Benny Applebaum: Exponentially-Hard gap-CSP and local PRG via Local Hardcore Functions

Is it possible to approximate the value of a 3-CNF formula to within a small constant factor in sub-exponential time?

This question was recently raised by (Dinur 2016; Manurangsi and Raghavendra 2016) who conjectured that the answer is negative. 

 

We will explore the validity of this new Gap-ETH assumption and show that it follows from the exponential hardness of finding a satisfying assignment for smooth 3-CNFs, where smoothness means that the number of satisfying assignments is not much smaller than the number of “almost-satisfying” assignments. 

We further show that the latter (“smooth-ETH”) assumption follows from the exponential hardness of solving constraint satisfaction problems over well-studied distributions, and, more generally, from the existence of any exponentially-hard locally-computable one-way function, confirming a conjecture of Dinur (ECCC 2016), confirming a conjecture of Dinur (ECCC 2016). 

 

Our reductions are inspired by classical cryptographic transformations from one-wayness to pseudorandomness. 

In particular, our main result is based on a new construction of general (Goldreich-Levin type) hardcore functions that, for any exponentially-hard one-way function, output linearly many hardcore bits, can be locally computed, and consume only a linear amount of random bits.