Top

Theory of Computing Systems

Published in:

01-08-2014

Pseudo-Random Graphs and Bit Probe Schemes with One-Sided Error

Author: Andrei Romashchenko

Published in: Theory of Computing Systems | Issue 2/2014

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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 “x∈A? ” can be answered very quickly. H. Buhrman, P.B. Miltersen, J. Radhakrishnan, and S. Venkatesh proposed a randomized bit-probe scheme that needs space of O(nlogm) bits. That scheme has a randomized algorithm processing queries; it needs to read only one randomly chosen bit from the memory to answer a query. For every x the answer is correct with high probability (with two-sided errors).

In this paper we slightly modify the bit-probe model of Buhrman et al. and consider schemes with a small auxiliary information in “cache” memory. In this model, we show that for the membership problem there exists a bit-probe scheme with one-sided error that needs space of O(nlog² m+poly(logm)) bits, which cannot be achieved in the model without cache. We also obtain a slightly weaker result (space of size n ^1+δpoly(logm) bits and two bit probes for every query) for a scheme that is effectively encodable.

previous article Improving the Space-Bounded Version of Muchnik’s Conditional Complexity Theorem via “Naive” Derandomization

next article An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

The same argument can be presented in a more standard framework, with a read-once input tape and an index tape of poly-logarithmic size. However, we believe that the argument becomes more intuitive when we allow many passes on the input tape.

Bloom, B.: Space-time trade-offs in hash coding with allowable errors. Commun. ACM 13(7), 422–426 (1970) CrossRefMATH

Pinsker, M.S.: On the complexity of a concentrator. In: 7th International Teletrafc Conference, pp. 318/1–318/4 (1973)

Bassalygo, L.A., Pinsker, M.S.: The complexity of an optimal non-blocking commutation scheme without reorganization. Probl. Inf. Transm. 9, 64–66 (1974)

Dyachkov, A.G., Rykov, V.V.: Bounds on the length of disjunctive codes. Probl. Inf. Transm. 18(3), 7–13 (1982) MathSciNet

Fredman, M.L., Komlós, J., Szemerédi, E.: Storing a sparse table with O(1) worst case access time. J. Assoc. Comput. Mach. 31(3), 538–544 (1984) CrossRefMATHMathSciNet

Erdös, P., Frankl, P., Füredi, Z.: Families of nite sets in which no set is covered by the union of r others. Isr. J. Math. 51, 79–89 (1985) CrossRefMATH

Håstad, J.: Almost optimal lower bounds for small depth circuits. In: Proc. of the 18th Annual ACM Symposium on Theory of Computing (STOC), pp. 6–20 (1986)

Siegel, A.: On universal classes of fast high performance hash functions, their time-space trade-off, and their applications. In: Proc. of 30th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 20–25 (1989) CrossRef

Nisan, N.: Pseudorandom generators for space-bounded computation. Combinatorica 12(4), 449–461 (1992). Preliminary version (1990) CrossRefMATHMathSciNet

10.

Fiat, A., Naor, M., Schmidt, J.P., Siegel, A.: Non-oblivious hashing. J. ACM 39, 764–782 (1992) CrossRefMATHMathSciNet

11.

Nisan, N., Wigderson, A.: Hardness vs randomness. J. Comput. Syst. Sci. 49(2), 149–167 (1994) CrossRefMATHMathSciNet

12.

Kahale, N.: Eigenvalues and expansion of regular graphs. J. ACM 42(5), 1091–1106 (1995) CrossRefMATHMathSciNet

13.

Siegel, A.: On universal classes of extremely random constant time hash functions and their time-space tradeoff. Technical report TR1995-684, Courant Institute, New York University, April (1995)

14.

Trevisan, L.: Construction of extractors using pseudo-random generators. In: Proc. of the 31st Annual ACM Symposium on Theory of Computing (STOC), pp. 141–148 (1999)

15.

Brodnik, A., Munro, J.I.: Membership in constant time and minimum space. SIAM J. Comput. 28(5), 1627–1640 (1999) CrossRefMATHMathSciNet

16.

Pagh, R.: Low redundancy in static dictionaries with O(1) worst case lookup time. In: Proc. of the 26th International Colloquium on Automata, Languages and Programming (ICALP), pp. 595–604 (1999) CrossRef

17.

Vitter, J.S.: External memory algorithms and data structures. ACM Comput. Surv. 33(2), 209–271 (2001) CrossRef

18.

Buhrman, H., Miltersen, P.B., Radhakrishnan, J., Srinivasan, V.: Are bitvectors optimal? SIAM J. Comput. 31(6), 1723–1744 (2002). Preliminary version, pp. 449–458 (2000) CrossRefMATHMathSciNet

19.

Ta-Shma, A., Umans, C., Zuckerman, D.: Loss-less condensers, unbalanced expanders, and extractors. In: Proc. of the 33rd Annual ACM Symposium on Theory of Computing (STOC), pp. 143–152 (2001)

20.

Pagh, R.: On the cell probe complexity of membership and perfect hashing. In: Proc. of the 33rd Annual ACM Symposium on Theory of Computing (STOC), pp. 425–432 (2001)

21.

Capalbo, M.R., Reingold, O., Vadhan, S.P., Wigderson, A.: Randomness conductors and constant-degree lossless expanders. In: Proc. of the 34th Annual ACM Symposium on Theory of Computing (STOC), pp. 659–668 (2002)

22.

Sivakumar, D.: Algorithmic derandomization via complexity theory. In: Proc. of the 34th Annual CM Symposium on Theory of Computing (STOC), pp. 619–626 (2002)

23.

Östlin, A., Pagh, R.: One-Probe search. In: Proc. of the 29th International Colloquium on Automata, Languages and Programming (ICALP), pp. 439–450 (2002) CrossRef

24.

Raz, R., Reingold, O., Vadhan, S.P.: Extracting all the randomness and reducing the error in Trevisan’s extractors. J. Comput. Syst. Sci. 65(1), 97–128 (2002) CrossRefMATHMathSciNet

25.

Ta-Shma, A.: Storing information with extractors. Inf. Process. Lett. 83, 267–274 (2002) CrossRefMATHMathSciNet

26.

Devroye, L., Morin, P.: Cuckoo hashing: further analysis. Inf. Process. Lett. 86, 215–219 (2003) CrossRefMATHMathSciNet

27.

Pagh, R., Rodler, F.: Cuckoo hashing. J. Algorithms 51, 122–144 (2004) CrossRefMATHMathSciNet

28.

Parvaresh, F., Vardy, A.: Correcting errors beyond the Guruswami-Sudan radius in polynomial time. In: Proc. of the 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 285–294 (2005)

29.

Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Am. Math. Soc. 43(4), 439–561 (2006) CrossRefMATHMathSciNet

30.

Vitter, J.S.: Algorithms and Data Structures for External Memory. Series on Foundations and Trends in Theoretical Computer Science. Now Publishers, Hanover (2008)

31.

Braverman, M.: Poly-logarithmic independence fools AC⁰ circuits. In: Proc. of the 27th IEEE Conference on Computational Complexity, pp. 3–8 (2009)

32.

Arbitman, Y., Naor, M., Segev, G.: De-amortized cuckoo hashing: provable Worst-Case performance and experimental results. In: Proc. of the 36th International Colloquium on Automata, Languages and Programming. ICALP, vol. 1, pp. 107–118 (2009) CrossRef

33.

Guruswami, V., Umans, C., Vadhan, S.: Unbalanced expanders and randomness extractors from Parvaresh–Vardy codes. J. ACM 56(4), 20:1–20:34 (2009) CrossRefMathSciNet

34.

Musatov, D.: Theorems about space-bounded Kolmogorov complexity obtained by “naive” derandomization. In: Proc. 6th International Computer Science Symposium (CSR), Russia, pp. 64–76 (2011)

35.

David, M., Papakonstantinou, P.A., Sidiropoulos, A.: How strong is Nisan’s pseudorandom generator? Inf. Process. Lett. 111(6), 804–808 (2011) CrossRefMATHMathSciNet

Title: Pseudo-Random Graphs and Bit Probe Schemes with One-Sided Error
Author: Andrei Romashchenko
Publication date: 01-08-2014
Publisher: Springer US
Published in: Theory of Computing Systems / Issue 2/2014
Print ISSN: 1432-4350
Electronic ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-012-9425-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 2/2014

Improving the Space-Bounded Version of Muchnik’s Conditional Complexity Theorem via “Naive” Derandomization

Learning Read-Constant Polynomials of Constant Degree Modulo Composites

The Equivalence of Sampling and Searching

Two-Way Automata Versus Logarithmic Space

Join-Reachability Problems in Directed Graphs

Editorial

Premium Partner