Creator

Created

Jan 15, 2024 3:34 PM

In this context, “better PoS” means one where decoding can be significantly faster.

Recall that a directed acyclic graph G is (e, d) predecessor (respectively, depth) robust if, no matter what e nodes are removed, there remains a single-sink subgraph (respectively, path) with d nodes. (We will also speak of fractional e and d, relative to the total number of nodes.)

**Question**: Can we build graphs of reasonable size (say, 2^{30} nodes) whose degree is reasonably low (say, below 100), for reasonably high e (something like 0.1 or 0.2 or even 0.5) and still get a nontrivial d, for reasonably large graphs (say, 2^30 nodes)?