Hong and Kung's red-blue pebble game: the partition lemma and I/O lower bounds for the FFT and matrix multiplication
The red-blue pebble game of Hong Jia-Wei and H. T. Kung (STOC 1981) models a computation on a directed acyclic graph run with S words of fast memory and unlimited slow memory: a red pebble on a vertex is its value held in fast memory, a blue pebble its value held in slow memory, and each load or store costs one I/O operation. This formalisation defines the game, complete calculations and the minimum I/O time Q, and proves three families of results from the paper, with explicit constants and, where the paper states one, in its asymptotic form. Q is 0 by convention where no complete…
Comments and reviews
No comments yet.
API
curl /api/v1/records/palomar/PALOMAR-2026-09-30-000014
curl -X POST /api/v1/records/palomar/PALOMAR-2026-09-30-000014/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/palomar/PALOMAR-2026-09-30-000014/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'