SIAM Journal on Computing · 2002 · 85 citations · 16 references
ComputingComputer EngineeringComputer ScienceAlgorithmsData StructuresTheory Of ComputationCachingCoding TheoryComputational ComplexityData CompressionRate-distortion TheoryBit VectorsBit-vector ConstraintsRate-distortion Bounds
... 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
16
Noam Nisan, Avi Wigderson · Journal of Computer and System Sciences · 1994 · 821 citations
Andrew Chi-Chih Yao · Journal of the ACM · 1981 · 359 citations · Full text