0.5 GB of SRAM is exactly what the Cuckatoo32 [1] Proof-of-Work scheme needs for optimal solving efficiency. Solutions are 42-cycles in random bipartite graphs of 2^32 edges on 2^32 + 2^32 nodes, which can be found by repeatedly removing edges that have only one adjacent edge. Tracking which nodes have incident edges takes 2^32 (completely randomly accessed) bits which is exactly 0.5GB. Another 0.5 GB is needed to track alive edges but those can be accessed serially for which DRAM suffices.

[1] https://github.com/tromp/cuckoo