A new connection between node and edge depth robust graphs

DOI10.4230/LIPICS.ITCS.2021.64MaRDI QIDQ7229353zbMATH OpenFDO

Authors Jeremiah Blocki, Mike Cinkoske

Publication date 15 April 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2021.64

zbMATH Keywords

depth robust graphsmemory hard functions

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Data-independent memory hard functions: new attacks and stronger constructions
• Depth-robust graphs and their cumulative memory complexity
• Efficiently computing data-independent memory-hard functions
• Explicit constructions of linear-sized superconcentrators
• Graph-theoretic properties in computational complexity
• Mathematical foundations of computer science 1977. Proceedings 6th symposium, Tatranska Lomnica, September 5-9, 1977
• Memory-hard functions from cryptographic primitives
• On sparse graphs with dense long paths
• Proofs of Catalytic Space
• Proofs of space
• Publicly verifiable proofs of sequential work
• Superconcentrators
• Sustained space complexity
• Tight proofs of space and replication

This page was built for publication: A new connection between node and edge depth robust graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7229353)