Assume that $NP\ne RP$. Gutfreund, Shaltiel, and Ta-Shma in [Computational Complexity 16(4):412-441 (2007)] have proved that for every randomized polynomial time decision algorithm $D$ for SAT there is a polynomial time samplable distribution such that $D$ errs with probability at least $1/6-\epsilon$ on a random formula chosen with respect to ... more >>>

Whether one-way functions (OWF) exist is arguably the most important
problem in Cryptography, and beyond. While lots of candidate
constructions of one-way functions are known, and recently also
problems whose average-case hardness characterize the existence of
OWFs have been demonstrated, the question of
whether there exists some \emph{worst-case hard problem} ... more >>>

Time-bounded conditional Kolmogorov complexity of a string $x$ given $y$, $K^t(x\mid y)$, is the length of a shortest program that, given $y$, prints $x$ within $t$ steps. The Chain Rule for conditional $K^t$ with error $e$ is the following hypothesis: there is a constant $c\in\mathbb{N}$ such that, for any strings ... more >>>