Beyond the Static Barrier for Ordinary Dynamic Approximate Membership

Qizhi Chen, Zhebei Shen, Zhehan Yu

We prove a strict space separation between static and ordinary dynamic approximate membership at every fixed error rate. For each fixed $\epsilon \in (0,1)$, a capacity-$n$ ordina…