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

by Benny Applebaum

Oded's comments

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 original abstract

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.


Back to list of Oded's choices.