Pseudo-random graphs and bit probe schemes with one-sided error

Andrei Romashchenko 1, *
* Auteur correspondant
1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We study probabilistic bit-probe schemes for the membership problem. Given a set A of at most n elements from the universe of size m we organize such a structure that queries of type "Is x in A?" can be answered very quickly. H.Buhrman, P.B.Miltersen, J.Radhakrishnan, and S.Venkatesh proposed a bit-probe scheme based on expanders. Their scheme needs space of $O(n\log m)$ bits, and requires to read only one randomly chosen bit from the memory to answer a query. The answer is correct with high probability with two-sided errors. In this paper we show that for the same problem there exists a bit-probe scheme with one-sided error that needs space of $O(n\log^2 m+\poly(\log m))$ bits. The difference with the model of Buhrman, Miltersen, Radhakrishnan, and Venkatesh is that we consider a bit-probe scheme with an auxiliary word. This means that in our scheme the memory is split into two parts of different size: the main storage of $O(n\log^2 m)$ bits and a short word of $\log^{O(1)}m$ bits that is pre-computed once for the stored set A and 'cached'. To answer a query "Is x in A?" we allow to read the whole cached word and only one bit from the main storage. For some reasonable values of parameters our space bound is better than what can be achieved by any scheme without cached data.
Type de document :
Communication dans un congrès
CSR: Computer Science Symposium in Russia, Jun 2011, Saint Petersburg, Russia. 6th International Computer Science Symposium in Russia, pp.50-63, 2011
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736119
Contributeur : Andrei Romashchenko <>
Soumis le : jeudi 27 septembre 2012 - 16:03:08
Dernière modification le : jeudi 24 mai 2018 - 15:59:23
Document(s) archivé(s) le : vendredi 16 décembre 2016 - 18:20:24

Fichier

bitprobe-arxiv.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00736119, version 1

Collections

Citation

Andrei Romashchenko. Pseudo-random graphs and bit probe schemes with one-sided error. CSR: Computer Science Symposium in Russia, Jun 2011, Saint Petersburg, Russia. 6th International Computer Science Symposium in Russia, pp.50-63, 2011. 〈lirmm-00736119〉

Partager

Métriques

Consultations de la notice

124

Téléchargements de fichiers

187