nach oben

Theory of Computing Systems

Erschienen in:

01.08.2014

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

verfasst von: Daniil Musatov

Erschienen in: Theory of Computing Systems | Ausgabe 2/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Many theorems about Kolmogorov complexity rely on existence of combinatorial objects with specific properties. Usually the probabilistic method gives such objects with better parameters than explicit constructions do. But the probabilistic method does not give “effective” variants of such theorems, i.e. variants for resource-bounded Kolmogorov complexity. We show that a “naive derandomization” approach of replacing these objects by the output of Nisan-Wigderson pseudo-random generator can give polynomial-space variants of such theorems.

Specifically, we improve the preceding polynomial-space analogue of Muchnik’s conditional complexity theorem. I.e., for all a and b there exists a program p of least possible length that transforms a to b and is simple conditional on b. Here all programs work in polynomial space and all complexities are measured with logarithmic accuracy instead of polylogarithmic one in the previous work.

Vorheriger Artikel The Equivalence of Sampling and Searching

Nächster Artikel Pseudo-Random Graphs and Bit Probe Schemes with One-Sided Error

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Ajtai, M.: Approximate counting with uniform constant-depth circuits. In: Advances in Computational Complexity Theory, pp. 1–20. American Mathematical Society, Providence (1993)

Buhrman, H., Fortnow, L., Laplante, S.: Resource bounded Kolmogorov complexity revisited. SIAM J. Comput. 31(3), 887–905 (2002) CrossRefMATHMathSciNet

Dvir, Z., Wigderson, A.: Kakeya sets, new mergers and old extractors. In: Proceedings of the 49th Annual FOCS08, pp. 625–633 (2008)

Guruswami, V., Umans, C., Vadhan, S.: Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. Journal of the ACM 56(4) (2009)

Li, M., Vitanyi, P.: An Introduction to Kolmogorov Complexity and Its Applications, 2nd edn. Springer, Berlin (1997) CrossRefMATH

Lu, C.-J., Reingold, O., Vadhan, S., Wigderson, A.: Extractors: optimal up to constant factors. In: 35th Annual ACM Symposium, STOC 2003, pp. 602–611 (2003)

Muchnik, An.: Conditional complexity and codes. Theor. Comput. Sci. 271(1–2), 97–109 (2002) CrossRefMATHMathSciNet

Musatov, D.: Improving the space-bounded version of Muchnik’s conditional complexity theorem via “naive” derandomization. In: Kulikov, A., Vereshchagin, N. (eds.) CSR. Lecture Notes in Computer Science, vol. 6651, pp. 64–76 (2011). Conference version of this paper, an online version is available at arXiv:1009.5108

Musatov, D.: Space-bounded Kolmogorov extractors. In: Hirsch, E., Karhumaki, J., Lepisto, A., Prilutskii, M. (eds.) CSR. Lecture Notes in Computer Science, vol. 7353, pp. 266–277 (2012)

10.

Musatov, D., Romashchenko, A., Shen, A.: Variations on Muchnik’s conditional complexity theorem. Theory Comput. Syst. 49(2), 227–245 (2011) CrossRefMATHMathSciNet

11.

Nisan, N.: Pseudorandom bits for constant depth circuits. Combinatorica 11(1), 63–70 (1991) CrossRefMATHMathSciNet

12.

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

13.

Radhakrishnan, J., Ta-Shma, A.: Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM J. Discrete Math. 13(1), 2–24 (2000) CrossRefMATHMathSciNet

14.

Reingold, O., Shaltiel, R., Wigderson, A.: Extracting randomness via repeated condensing. SIAM J. Comput. 35(5), 1185–1209 (2006) CrossRefMATHMathSciNet

15.

Romashchenko, A.: Pseudo-random graphs and bit probe schemes with one-sided error. In: Kulikov, A., Vereshchagin, N. (eds.) CSR. Lecture Notes in Computer Science, vol. 6651, pp. 50–63 (2011)

16.

Slepian, D., Wolf, J.K.: Noiseless coding of correlated information sources. IEEE Trans. Inf. Theory 19, 471–480 (1973) CrossRefMATHMathSciNet

17.

Trevisan, L.: Extractors and pseudorandom generators. J. ACM 48(4), 860–879 (2001) CrossRefMATHMathSciNet

18.

Uspensky, V.A., Vereshchagin, N.K., Shen, A.: Kolmogorov Complexity and Algorithmic Randomness. An unpublished book. (available in Russian at http://www.lif.univ-mrs.fr/~ashen/nafit/kolmbook.pdf, partial translation to English is available at http://kolmsem.math.ru/files/kolmeng.pdf

19.

Viola, E.: Randomness buys depth for approximate counting. In: Proceedings of 52nd IEEE FOCS, pp. 230–239 (2011)

20.

Zimand, M.: Extracting the Kolmogorov complexity of strings and sequences from sources with limited independence. In: Proceedings of 26th STACS, pp. 697–708 (2009)

21.

Zimand, M.: Impossibility of independence amplification in Kolmogorov complexity theory. In: Proceedings of MFCS 2010. LNCS, vol. 6281, pp. 701–712 (2010)

22.

Zimand, M.: Symmetry of information and bounds on nonuniform randomness extraction via Kolmogorov extractors. In: Proceedings of 26th IEEE Conference in Computational Complexity, pp. 148–156 (2011)

23.

Zimand, M.: On the optimal compression of sets in PSPACE. In: Proceedings of 18th International Symposium on Fundamentals of Computation Theory, pp. 65–77 (2011) CrossRef

Titel: Improving the Space-Bounded Version of Muchnik’s Conditional Complexity Theorem via “Naive” Derandomization
verfasst von: Daniil Musatov
Publikationsdatum: 01.08.2014
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 2/2014
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-012-9432-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2014

Editorial

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

Learning Read-Constant Polynomials of Constant Degree Modulo Composites

The Complexity of Solving Reachability Games Using Value and Strategy Iteration

Join-Reachability Problems in Directed Graphs

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