## 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.