4 papers
A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower Bounds
Paul Beame, Blake Holman, Niels Kornerup
Time and space (memory) are two of the most important measures of cost in computation, even more so for quantum computation. Yet, our tools for proving unconditional quantum tradeo…
Data-Dependent Memory-Hard Functions: Sustained Space and Cumulative Complexity Trade-offs in the Parallel Random Oracle Model
Jeremiah Blocki, Blake Holman
Memory-Hard Functions (MHFs) protect passwords and other low-entropy secrets against brute-force attacks. Sustained space complexity (SSC), the strongest natural formalization of m…
Quantum Search with In-Place Queries
Blake Holman, Ronak Ramachandran, Justin Yirka
Quantum query complexity is typically characterized in terms of XOR queries |x,y> to |x,y+f(x)> or phase queries, which ensure that even queries to non-invertible functions are uni…
The Parallel Reversible Pebbling Game: Analyzing the Post-Quantum Security of iMHFs
Jeremiah Blocki, Blake Holman, Seunghoon Lee
The classical (parallel) black pebbling game is a useful abstraction which allows us to analyze the resources (space, space-time, cumulative space) necessary to evaluate a function…