Submit progress

on Do one-way functions exist?

The statement

Does there exist a polynomial-time computable $f:\{0,1\}^* \to \{0,1\}^*$ such that for every probabilistic polynomial-time adversary $A$ and every polynomial $p$ , for all sufficiently large $n$ ,

\Pr_{x \sim \{0,1\}^n}\!\left[A(f(x)) \in f^{-1}(f(x))\right] < \frac{1}{p(n)}?

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.