On the power of two, three and four probes

ABSTRACT

An adaptive (n, m, s, t)-scheme is a deterministic scheme for encoding a vector X of m bits with at most n ones by a vector Y of s bits, so that any bit of X can be determined by t adaptive probes to Y. A non-adaptive (n, m, s, t)-scheme is defined analogously. The study of such schemes arises in the investigation of the static membership problem in the bitprobe model. Answering a question of Buhrman, Miltersen, Radhakrishnan and Venkatesh [SICOMP 2002] we present adaptive (n, m, s, 2) schemes with s < m for all n satisfying 4n² + 4n < m and adaptive (n, m, s, 2) schemes with s = o(m) for all n = o(log m). We further show that there are adaptive (n, m, s, 3)-schemes with s = o(m) for all n = o(m), settling a problem of Radhakrishnan, Raman and Rao [ESA 2001], and prove that there are non-adaptive (n, m, s, 4)-schemes with s = o(m) for all n = o(m). Therefore, three adaptive probes or four non-adaptive probes already suffice to obtain a significant saving in space compared to the total length of the input vector. Lower bounds are discussed as well.

REFERENCES

• 1: Noga Alon , Asaf Shapira†, On An Extremal Hypergraph Problem Of Brown, Erdős And Sós, Combinatorica, v.26 n.6, p.627-645, December 2006 [doi>10.1007/s00493-006-0035-9]
• 2: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 3: B. Bollobás, Random Graphs, Academic Press, 1985.
• 4: A. Broder and M. Mitzenmacher, Network applications of Bloom filters: a survey, Internet Mathematics Vol. 1, No. 4: 485--509, 2004.
• 5: W. G. Brown, P. Erdős and V. T. Sós, Some extremal problems on r-graphs, New Directions in the Theory of Graphs, Proc. 3^rd Ann Arbor Conference on Graph Theory, Academic Press, New York, 1973, 55--63.
• 6: W. G. Brown, P. Erdős and V. T. Sós, On the existence of triangulated spheres in 3-graphs and related problems, Periodica Mathematica Hungaria, 3 (1973), 221--228.
• 7: H. Buhrman , P. B. Miltersen , J. Radhakrishnan , S. Venkatesh, Are Bitvectors Optimal?, SIAM Journal on Computing, v.31 n.6, p.1723-1744, 2002 [doi>10.1137/S0097539702405292]
• 8: Michael Capalbo , Omer Reingold , Salil Vadhan , Avi Wigderson, Randomness conductors and constant-degree lossless expanders, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510003]
• 9: F. Lazebnik, V. A. Ustimenko and A. J. Woldar, A new series of dense graphs of high girth, Bull. Amer. Math. Soc. (N.S.), 32 (1995), 73--79.
• 10: M. Minsky and S. Papert, Perceptrons, MIT Press, Cambridge, MA 1969.
• 11: Jaikumar Radhakrishnan , Venkatesh Raman , S. Srinivasa Rao, Explicit Deterministic Constructions for Membership in the Bitprobe Model, Proceedings of the 9th Annual European Symposium on Algorithms, p.290-299, August 28-31, 2001
• 12: I. Z. Ruzsa and E. Szemerédi, Triple systems with no six points carrying three triangles, in Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai 18, Volume II, 939--945.
• 13: G. N. Sárközy and S. M. Selkow, On a Turán-type hypergraph problem of Brown, Erdős and T. Sós, Discrete Math. 297 (2005), 190--195

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.0 General

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms