This paper is very rich in results and ideas, and the following abstract outlines some of them. Let me stress that ``smooth ETH'' means that the ETH holds in a way that is related to the smoothness parameter outlined below (i.e., if the almost satisfiable instances are more numerous by a factor of $F$ then hardness should hold wrt time $F^5$ times some exponential bound. In any case, the assumption follows not only from exponentially-hard (locally-computable) one-way functions, but rather from such that are one-way in a weak sense that hardness holds only for an exponentially vanishing (weighted) fraction of the range. Note taht such weak one-way functions are not known to yield strong ones in the current setting.
The gap-ETH assumption (Dinur 2016; Manurangsi and Raghavendra 2016) asserts that it is exponentially-hard to distinguish between a satisfiable 3-CNF formula and a 3-CNF formula which is at most 0.99-satisfiable. We show that this assumption follows from the exponential hardness of finding a satisfying assignment for *smooth* 3-CNFs. Here 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. This confirms a conjecture of Dinur (ECCC 2016).
We also prove an analogous result in the cryptographic setting. Namely, we show that the existence of exponentially-hard locally-computable pseudorandom generator with linear stretch (el-PRG) follows from the existence of an exponentially-hard locally-computable ``almost regular'' one-way functions.
None of the above assumptions (gap-ETH and el-PRG) was previously known to follow from the hardness of a search problem. Our results are based on a new construction of general (GL-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.
See ECCC TR17-063. See also proceedings of FOCS'17.