Getting Harder All the Time?
summary
Survey of two concrete research directions: one studies proof-of-work style puzzles that are only moderately hard — intended bounds here are explicit upper and lower running-time thresholds, resistance to amortization across many puzzles, and applications to spam mitigations, DoS and digital coins (examples: Dwork, reCAPTCHA). The other asks whether composing many very simple permutations (e.g., 3-bit moves) yields a pseudorandom permutation: known results give polynomial composition → k-wise independence; conjecture asserts that achieving four-wise independence already implies pseudorandomness (card-shuffle analogs and Diaconis’ “seven shuffles” appear).
AI-written summary · about