Counting Dependent and Independent Strings

• Autorzy: Zimand M.

Identyfikatory

DOI

10.3233/FI-2014-1027

• Języki publikacji: EN

Abstrakty

EN

We derive quantitative results regarding sets of n-bit strings that have different dependency or independency properties. Let C(x) be the Kolmogorov complexity of the string x. A string y has α dependency with a string x if C(y) − C(y | x) ≥ α. A set of strings {x₁, . . . , x_t} is pairwise α-independent if for all i ≠ j, C(x_i) − C(x_i | x_j < α. A tuple of strings (x₁, . . . , x_t) is mutually α-independent if C(xπ(1) . . . xπ(t)) > C(x₁)+. . .+C(x_t) − α, for every permutation π of [t]. We show that: • For every n-bit string x with complexity C(x) ≥ α + 7 log n, the set of n-bit strings that have α dependency with x has size at least (1/poly(n))2n−α. In case α is computable from n and C(x) ≥ α + 12 log n, the size of the same set is at least (1/C)2^n−α − poly(n)2^α, for some positive constant C. • There exists a set of n-bit strings A of size poly(n)2α such that any n-bit string has α-dependency with some string in A. • If the set of n-bit strings {x₁, . . . , x_t} is pairwise α-independent, then t ≤ poly(n)2^α. This bound is tight within a poly(n) factor, because, for every n, there exists a set of n-bit strings {x₁, . . . , x_t} that is pairwise α-dependent with t = (1/poly(n)) · 2α (for all α ≥ 5 log n). • If the tuple of n-bit strings (x₁, . . . , x_t) is mutually α-independent, then t ≤ poly(n)2^α (for all α ≥ 7 log n + 6).

Słowa kluczowe

EN

counting; dependence; independence; string theory; set theory; kolmogorov complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 131, nr 3-4
• Strony: 485--497
• Opis fizyczny: Bibliogr 22 poz.

Twórcy

autor

Zimand M.

• Department of Computer and Information Sciences, Towson University, Baltimore, MD, USA

Bibliografia

• [1] Barak, B., Impagliazzo, R., Wigderson, A.: Extracting randomness using few independent sources, Proceedings of the 36th ACM Symposium on Theory of Computing, 2004.
• [2] Barak, B., Kindler, G., Shaltiel, R., Sudakov, B., Wigderson, A.: Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors, Proceedings of the 37th ACM Symposium on Theory of Computing, 2005.
• [3] Bourgain, J.: More on the sum-product phenomenon in prime fields and its applications, International Journal of Number Theory, 1, 2005, 1–32.
• [4] Calude, C.: Information and Randomness: An Algorithmic Perspective, Springer-Verlag, 2002, 2nd edition, 1st edition in 1994.
• [5] Chang, C., Lyuu, Y., Ti, Y., Shen, A.: Sets of k-independent sets, International Journal of Foundations of Computer Science, 21(3), 2010, 321–327.
• [6] Downey, R., Hirschfeldt, D.: Algorithmic randomness and complexity, Springer Verlag, 2010.
• [7] Fortnow, L., Hitchcock, J., Pavan, A., Vinodchandran,N.,Wang, F.: Extracting Kolmogorov complexity with applications to dimension zero-one laws, Proceedings of the 33rd International Colloquium on Automata, Languages, and Programming, Springer-Verlag Lecture Notes in Computer Science #4051, Berlin, 2006.
• [8] Hitchcock, J., Pavan, A., Vinodchandran,N.: KolmogorovComplexity in Randomness Extraction, Electronic Colloquium on Computational Complexity (ECCC), (09-071), 2009.
• [9] Jukna, S.: Extremal Combinatorics, Springer Verlag, 2001.
• [10] Li, M., Vitanyi, P.: An introduction to Kolmogorov complexity and its applications, Springer-Verlag, 2008, 3rd edition. 1st edition in 1993.
• [11] Rao, A.: Extractors for a constant number of polynomially small min-entropy independent sources, Proceedings of the 38th ACM Symposium on Theory of Computing, 2006.
• [12] Raz, R.: Extractors with weak random seeds, STOC (H. N. Gabow, R. Fagin, Eds.), ACM, 2005, ISBN 1-58113-960-8.
• [13] Shen, A.: Algorithmic Information Theory and Kolmogorov complexity, Technical Report 2000-034,Uppsala Universitet, December 2000.
• [14] Turán, P.: On an extremal problem in graph theory, Math.Fiz.Lapok, 48, 1941, 436–452, In Hungarian.
• [15] Wei, V.: A lower bound on the stability number of a simple graph, Technical Report 81-11217-9, Bell Laboratories, 1981.
• [16] Zimand, M.: Two Sources Are Better Than One for Increasing the Kolmogorov Complexity of Infinite Sequences, CSR (E. A. Hirsch, A. A. Razborov, A. L. Semenov, A. Slissenko, Eds.), 5010, Springer, 2008, ISBN 978-3-540-79708-1.
• [17] Zimand, M.: Extracting the Kolmogorov complexity of strings and sequences from sources with limited independence, Proceedings 26th STACS, Freiburg, Germany, February 26–29 2009.
• [18] Zimand, M.: On Generating Independent Random Strings, CiE (K. Ambos-Spies, B. Löwe, W. Merkle, Eds.), 5635, Springer, 2009, ISBN 978-3-642-03072-7.
• [19] Zimand, M.: Counting Dependent and Independent Strings, MFCS, 6281, Springer, 2010.
• [20] Zimand,M.: Impossibility of IndependenceAmplification in Kolmogorov Complexity Theory, MFCS, 6281, Springer, 2010.
• [21] Zimand, M.: Possibilities and impossibilities in Kolmogorov complexity extraction, SIGACT News, 41(4), December 2010, 74–94.
• [22] Zvonkin, A., Levin, L.: The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms, Russian Mathematical Surveys, 25(6), 1970, 83–124.