Are Bitvectors Optimal?

Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan

SIAM Journal on Computing · 2002 · 85 citations · 16 references

Concepts

Abstract

... We show lower bounds that come close to our upper bounds (for a large range of n and ffl): Schemes that answer queries with just one bitprobe and error probability ffl must use \\Omega ( nffl log(1=ffl) log m) bits of storage; if the error is restricted to queries not in S, then the scheme must use \\Omega ( n2ffl2 log(n=ffl) log m) bits of storage. We also

References

16