On algorithmic statistics for space-bounded algorithms
From MaRDI portal
DOI10.1007/s00224-018-9845-6zbMath1435.68129arXiv1702.08084OpenAlexW2792491466MaRDI QIDQ5919540
Publication date: 4 July 2019
Published in: Theory of Computing Systems, Computer Science – Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1702.08084
Kolmogorov complexityderandomizationalgorithmic statisticscomputational complexity theoryNisan-Wigderson generator
Foundations and philosophical topics in statistics (62A01) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Randomized algorithms (68W20)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Pseudorandom bits for constant depth circuits
- \(\text{RL}\subseteq \text{SC}\)
- Hardness vs randomness
- Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization
- Resource-Bounded Kolmogorov Complexity Revisited
- Around Kolmogorov Complexity: Basic Notions and Results
- Algorithmic Statistics: Forty Years Later
- Parity, circuits, and the polynomial-time hierarchy
- Kolmogorov's Structure Functions and Model Selection
- Kolmogorov Complexity and Algorithmic Randomness
- Rate Distortion and Denoising of Individual Data Using Kolmogorov Complexity
- Three approaches to the quantitative definition of information*
- An introduction to Kolmogorov complexity and its applications
- On algorithmic statistics for space-bounded algorithms
This page was built for publication: On algorithmic statistics for space-bounded algorithms
