A central open problem in complexity theory concerns the question of
whether all efficient randomized algorithms can be simulated by
efficient deterministic algorithms. The celebrated ``hardness
v.s. randomness” paradigm pioneered by Blum-Micali (SIAM JoC’84),
Yao (FOCS’84) and Nisan-Wigderson (JCSS’94) presents hardness
assumptions under which $\prBPP = \prP$, but these hardness ... more >>>

A central open problem in complexity theory concerns the question of whether all efficient randomized algorithms can be simulated by efficient deterministic algorithms. We consider this problem in the context of promise problems (i.e,. the $\prBPP$ v.s. $\prP$ problem) and show that for all sufficiently large constants $c$, the following ... more >>>

We show equivalence between the existence of one-way
functions and the existence of a \emph{sparse} language that is
hard-on-average w.r.t. some efficiently samplable ``high-entropy''
distribution.
In more detail, the following are equivalent:
- The existentence of a $S(\cdot)$-sparse language $L$ that is
hard-on-average with respect to some samplable ... more >>>

We present the first natural $\NP$-complete problem whose average-case hardness w.r.t. the uniform distribution over instances implies the existence of one-way functions (OWF). In fact, we prove that the existence of OWFs is \emph{equivalent} to mild average-case hardness of this $\NP$-complete problem. The problem, which originated in the 1960s, is ... more >>>

Liu and Pass (FOCS'20) recently demonstrated an equivalence between the existence of one-way functions (OWFs) and mild average-case hardness of the time-bounded Kolmogorov complexity problem. In this work, we establish a similar equivalence but to a different form of time-bounded Kolmogorov Complexity---namely, Levin's notion of Kolmogorov Complexity---whose hardness is closely ... more >>>

Let $\mktp[s]$ be the set of strings $x$ such that $K^t(x) \leq s(|x|)$, where $K^t(x)$ denotes the $t$-bounded Kolmogorov complexity of the truthtable described by $x$. Our main theorem shows that for an appropriate notion of mild average-case hardness, for every $\varepsilon>0$, polynomial $t(n) \geq (1+\varepsilon)n$, and every ``nice'' class ... more >>>

We prove the equivalence of two fundamental problems in the theory of computation:

- Existence of one-way functions: the existence of one-way functions (which in turn are equivalent to pseudorandom generators, pseudorandom functions, private-key encryption schemes, digital signatures, commitment schemes, and more).

- Mild average-case hardness of $K^{poly}$-complexity: ... more >>>

Consider the following two fundamental open problems in complexity theory: (a) Does a hard-on-average language in $\NP$ imply the existence of one-way functions?, or (b) Does a hard-on-average language in NP imply a hard-on-average problem in TFNP (i.e., the class of total NP search problem)? Our main result is that ... more >>>