BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Drupal iCal API//EN
X-WR-CALNAME:Events items teaser
X-WR-TIMEZONE:America/Toronto
BEGIN:VTIMEZONE
TZID:America/Toronto
X-LIC-LOCATION:America/Toronto
BEGIN:DAYLIGHT
TZNAME:EDT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
DTSTART:20260308T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20251102T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:69ce93993f8de
DTSTART;TZID=America/Toronto:20260313T153000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20260313T163000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq
 uium-seunghoon-lee-parallel-reversible-pebbling
SUMMARY:Tutte Colloquium -Seunghoon Lee-Parallel Reversible Pebbling:\nTime
 -Space Tradeoffs on DAGs (with Cryptographic Motivation)
CLASS:PUBLIC
DESCRIPTION:SPEAKER:\n Seunghoon Lee\n\nAFFILIATION:\n University of Waterl
 oo\n\nLOCATION:\n MC 5501\n\nABSTRACT: The (parallel) pebbling game is a 
 useful abstraction for\nanalyzing the resources (e.g.\, space\, space-time
 \, amortized\nspace-time) needed to evaluate a function f with a static\nd
 ata-dependency graph G on a (parallel) computer. The underlying\nquestion 
 is purely combinatorial: what tradeoffs does a directed\nacyclic graph (DA
 G) force between storing intermediate values and\nrecomputing them? This v
 iewpoint has been particularly influential in\ncryptography\, where many 
 “Memory-Hard Function” (MHF)\nconstructions can be modeled by evaluati
 ng a fixed DAG.\n\nClassical pebbling\, however\, does not capture an esse
 ntial constraint\nin quantum/reversible computation: intermediate informat
 ion cannot be\ndiscarded freely\, so cleanup must respect the dependency s
 tructure.\nWhile sequential reversible pebbling has been used to study spa
 ce-time\ntradeoffs in sequential settings\, it does not reflect the space-
 time\ntradeoffs for parallel quantum/reversible algorithms. To model this\
 ,\nwe introduce the parallel reversible pebbling game and use it to\nanaly
 ze reversible space-time and amortized costs for important graph\nfamilies
 \, including line graphs and structured DAGs arising in MHF\nconstructions
  (e.g.\, Argon2i and DRSample). \nThe talk highlights two core results: Fi
 rst\, we give a lower bound on\nthe reversible amortized space-time cost f
 or a line graph\, which\nyields a separation between classical and reversi
 ble pebbling costs\,\nshowing a super-constant (yet sub-polynomial) gap. S
 econd\, this\noverhead is nevertheless controlled: we show that any classi
 cal\nparallel pebbling can be transformed into a reversible one with only 
 a\nsub-polynomial loss. This generic transformation serves as a central\nt
 ool for analyzing broader graph families. \nThe talk will focus on the com
 binatorial aspects of cryptographic\napplications\; no background in crypt
 ography is assumed. Based on joint\nwork with Jeremiah Blocki and Blake Ho
 lman: The Parallel Reversible\nPebbling Game: Analyzing the Post-Quantum S
 ecurity of iMHFs (TCC\n2022)\, and The Impact of Reversibility on Parallel
  Pebbling (EUROCRYPT\n2025).
DTSTAMP:20260402T160441Z
END:VEVENT
END:VCALENDAR