High Parallel Complexity Graphs and Memory-Hard Functions
From MaRDI portal
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Cryptography (94A60)
Recommendations
- Parallel computations on graphs
- scientific article; zbMATH DE number 1985710
- Parallel computations on a graph
- scientific article; zbMATH DE number 4128411
- Parallel graph algorithms for hypercube computers
- scientific article; zbMATH DE number 3972201
- Efficient Parallel Algorithms for a Class of Graph Theoretic Problems
- Efficient parallel algorithms for graph problems
- scientific article; zbMATH DE number 4068310
- scientific article; zbMATH DE number 3905859
Cites work
- Approximate distance oracles
- Approximate distance oracles with constant query time
- Automata, Languages and Programming
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Fast C-K-R partitions of sparse graphs
- Near-Linear Time Construction of Sparse Neighborhood Covers
- On approximate distance labels and routing schemes with affine stretch
- On sparse spanners of weighted graphs
- Ramsey partitions and proximity data structures
- Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
- Shortest-path queries in static networks
Cited in
(36)- Provable time-memory trade-offs: symmetric cryptography against memory-bounded adversaries
- Static-memory-hard functions, and modeling the cost of space vs. time
- Sustained space complexity
- Nullstellensatz size-degree trade-offs from reversible pebbling
- Tight time-space lower bounds for finding multiple collision pairs and their applications
- SPARKs: succinct parallelizable arguments of knowledge
- Password hashing and preprocessing
- Rifflescrambler -- a memory-hard password storing function
- The cost of adaptivity in security games on graphs
- Efficiently computing data-independent memory-hard functions
- Balloon hashing: a memory-hard function providing provable protection against sequential attacks
- Proof of space from stacked expanders
- Cumulative space in black-white pebbling and resolution
- Nullstellensatz size-degree trade-offs from reversible pebbling
- Depth-robust graphs and their cumulative memory complexity
- Scrypt is maximally memory-hard
- On the complexity of \textsf{scrypt} and proofs of space in the parallel random oracle model
- Verifiable capacity-bound functions: a new primitive from Kolmogorov complexity. (Revisiting space-based security in the adaptive setting)
- Parallelizable delegation from LWE
- Memory-hard puzzles in the standard model with applications to memory-hard functions and resource-bounded locally decodable codes
- Time-release cryptography from minimal circuit assumptions
- Sustained space and cumulative complexity trade-offs for data-dependent memory-hard functions
- The parallel reversible pebbling game: analyzing the post-quantum security of iMHFs
- Bandwidth-Hard Functions: Reductions and Lower Bounds
- PURED: a unified framework for resource-hard functions
- Trapdoor memory-hard functions
- Advancing scalability in decentralized storage: a novel approach to proof-of-replication via polynomial evaluation
- On sequential functions and fine-grained cryptography
- Can verifiable delay functions be based on random oracles?
- The impact of reversibility on parallel pebbling
- Cumulative memory lower bounds for randomized and quantum computation
- On graphs of incremental proofs of sequential work
- Space-lock puzzles and verifiable space-hard functions from root-finding in sparse polynomials
- Space-deniable proofs
- Provably memory-hard proofs of work with memory-easy verification
- Parallel spooky pebbling makes Regev factoring more practical
This page was built for publication: High Parallel Complexity Graphs and Memory-Hard Functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941555)
