When Pebbles Are Not Atomic: A Polynomial Separation Between Pure and Entangled Pebbling↗ (원문, 새 창)

본문 미리보기

arXiv:2610.27249v1 Announce Type: new Abstract: Graph pebbling is the model in which the memory cost of memory-hard functions and proofs of space is measured, and pebbling lower bounds are the main way to argue that such constructions are secure. It has long seemed that the model is faithful to reality. It is known that it is not exact: an adversary who stores encoded information instead of whole values can do better, but so far only by small factors: a factor of 1.5 in the work that introduced