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

Tuesday, April 10, 2018 - 4:00pm to 5:00pm
Light Refreshments at 3:45pm
Patil/Kiva G449
Benny Applebaum
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. 
We also show that such hardcore functions have several other useful applications in cryptography and complexity theory.