saiajc

Longest common subsequence can be solved in at most quadratic time via dynamic programming.

Kleinberg's HITS algorithm actually came first. PageRank simplified HITS and made it more practical, by performing the ranking mechanism in batch mode for the entire web graph. If you read the original HITS paper, you'll see that HITS computes the top two eigenvectors for the cluster of all pages containing the query word (and pages pointing to those pages). Computing new eigenvectors for every search query obviously is much slower than PageRank.

Thanks - this comment nicely summarizes the math involved here!

How can we defend Blockchains and peer-to-peer systems, when no central authority provides admission control? Resource-burning (proof-of-work, proof-of-state, CAPTCHAs) is one of the most used tools to defend such systems, but it is currently poorly understood mathematically. In this talk, I survey recent research to better understanding resource burning, in order to reduce its cost, and thereby improve system security.

Keywords: Distributed algorithms, game theory, costly signaling, money burning, Sybil attack, blockchains, cryptocurrencies, peer-to-peer.