On Algorithmic Statistics for Space-bounded Algorithms
- 6 February 2018
- journal article
- research article
- Published by Springer Nature in Theory of Computing Systems
- Vol. 63 (4) , 833-848
Abstract
No abstract availableKeywords
All Related Versions
Funding Information
- Russian Foundation for Basic Research (16-01-00362)
- Agence Nationale de la Recherche (15-CE40-0016-01)
- Young Russian Mathematics
- Russian Academic Excellence Project ‘5-100’
- MK (MK-5379.2018.1)
This publication has 15 references indexed in Scilit:
- Algorithmic Statistics: Forty Years Later2016
- Around Kolmogorov Complexity: Basic Notions and Results2015
- Improving the Space-Bounded Version of Muchnik’s Conditional Complexity Theorem via “Naive” DerandomizationTheory of Computing Systems, 2012
- Kolmogorov's Structure Functions and Model SelectionIEEE Transactions on Information Theory, 2004
- Resource-Bounded Kolmogorov Complexity RevisitedSIAM Journal on Computing, 2001
- Hardness vs randomnessJournal of Computer and System Sciences, 1994
- Pseudorandom bits for constant depth circuitsCombinatorica, 1991
- Parity, circuits, and the polynomial-time hierarchyTheory of Computing Systems, 1984
- Relationships between probabilistic and deterministic tape complexityLecture Notes in Computer Science, 1981
- Book Review: The theory of error-correcting codes.Bulletin of the American Mathematical Society, 1978