Memory-hard function: Difference between revisions

Revision as of 19:41, 26 December 2022

Revision as of 19:52, 26 December 2022

Line 7:

There are different ways to measure the memory hardness of a function, and a commonly seen measure is Cumulative Memory Complexity (CMC). In a parallel model, CMC is the sum of the memory required to compute a function over every time step of the computation.<ref>(AS15) Alwen, Serbineko, [https://eprint.iacr.org/2014/238.pdf ''High Parallel Complexity Graphs and Memory-Hard Functions''], 2015</ref><ref>{{cite arXiv |last1=Alwen |first1=Joel |last2=Blocki |first2=Jeremiah |last3=Pietrzak |first3=Krzysztof |date=2017-07-07 |title=Sustained Space Complexity |class=cs.CR |eprint=1705.05313 }}</ref>

AnotherOther viable measuremeasures isare integrating memory against physical time.<ref>(MO16) Moran, Orlov, [https://eprint.iacr.org/2016/035.pdf ''Simple Proofs of Space-Time and Rational Proofs of Storage''], 2016</ref>, and memory [[bandwidth (computing)|bandwidth]] consumption on a memory bus.<ref>(BR18) Blocki, Ren, [https://eprint.iacr.org/2018/221.pdf ''Bandwidth-Hard Functions: Reductions and Lower Bounds''], 2018</ref> Refer to functions requiring high memory bandwidth as "bandwidth-hard functions."

Yet another measure is the memory [[bandwidth (computing)|bandwidth]] consumption on a memory bus.<ref>(BR18) Blocki, Ren, [https://eprint.iacr.org/2018/221.pdf ''Bandwidth-Hard Functions: Reductions and Lower Bounds''], 2018</ref> Functions that require high memory bandwidth are also called "bandwidth-hard functions".

== Motivation ==