Skip to main content
2 votes

How to intuitively express the hardness of Minicrypt and Cryptomania?

The existence of (trapdoor) OWF implies that there are NP relations that are hard on average. But the difference of both worlds is no longer about the hardness of NP. It is much more about the ...
lamontap's user avatar
  • 1,010
2 votes

Hardness assumption: an NP-complete problem whose ratio of hard instances do not tend to zero?

Let us define the distance function of two languages $L, L'$ as $$ dist(n)= |L\Delta L'|_n$$ which means the number of $n$-bit strings in the symmetric difference $L\Delta L'$. If property ${\text P}$ ...
Andras Farago's user avatar
1 vote

ETH based lower bound for $k$-COLORING of bounded degree graph

The result mentioned in the question can be obtained by a chain of two standard reductions. The simplest reduction for $k$-COLORABILITY $\leq_p$ $(k+1)$-COLORABILITY (namely, adding a universal vertex)...

Only top scored, non community-wiki answers of a minimum length are eligible