---
res:
  bibo_abstract:
  - We develop new theoretical tools for proving lower-bounds on the (amortized) complexity
    of certain functions in models of parallel computation. We apply the tools to
    construct a class of functions with high amortized memory complexity in the parallel
    Random Oracle Model (pROM); a variant of the standard ROM allowing for batches
    of simultaneous queries. In particular we obtain a new, more robust, type of Memory-Hard
    Functions (MHF); a security primitive which has recently been gaining acceptance
    in practice as an effective means of countering brute-force attacks on security
    relevant functions. Along the way we also demonstrate an important shortcoming
    of previous definitions of MHFs and give a new definition addressing the problem.
    The tools we develop represent an adaptation of the powerful pebbling paradigm
    (initially introduced by Hewitt and Paterson [HP70] and Cook [Coo73]) to a simple
    and intuitive parallel setting. We define a simple pebbling game Gp over graphs
    which aims to abstract parallel computation in an intuitive way. As a conceptual
    contribution we define a measure of pebbling complexity for graphs called cumulative
    complexity (CC) and show how it overcomes a crucial shortcoming (in the parallel
    setting) exhibited by more traditional complexity measures used in the past. As
    a main technical contribution we give an explicit construction of a constant in-degree
    family of graphs whose CC in Gp approaches maximality to within a polylogarithmic
    factor for any graph of equal size (analogous to the graphs of Tarjan et. al.
    [PTC76, LT82] for sequential pebbling games). Finally, for a given graph G and
    related function fG, we derive a lower-bound on the amortized memory complexity
    of fG in the pROM in terms of the CC of G in the game Gp.@eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Joel F
      foaf_name: Alwen, Joel F
      foaf_surname: Alwen
      foaf_workInfoHomepage: http://www.librecat.org/personId=2A8DFA8C-F248-11E8-B48F-1D18A9856A87
  - foaf_Person:
      foaf_givenName: Vladimir
      foaf_name: Serbinenko, Vladimir
      foaf_surname: Serbinenko
  bibo_doi: 10.1145/2746539.2746622
  dct_date: 2015^xs_gYear
  dct_identifier:
  - UT:000485296600063
  dct_language: eng
  dct_publisher: ACM@
  dct_title: High parallel complexity graphs and memory-hard functions@
...