| Publication | Date of Publication | Type |
|---|
| Optimal coding theorems in time-bounded Kolmogorov complexity | 2024-06-24 | Paper |
scientific article; zbMATH DE number 7650906 (Why is no real title available?)
(available as arXiv preprint) | 2023-02-07 | Paper |
Effective category and measure in abstract complexity theory
Fundamentals of Computation Theory | 2022-12-09 | Paper |
| An operational characterization of mutual information in algorithmic information theory | 2021-07-28 | Paper |
An operational characterization of mutual information in algorithmic information theory
Journal of the ACM | 2020-02-11 | Paper |
Secret key agreement from correlated data, with no prior information
(available as arXiv preprint) | 2019-10-08 | Paper |
Distributed Compression through the Lens of Algorithmic Information Theory: A Primer
Mathematics Almost Everywhere | 2019-07-04 | Paper |
List approximation for increasing Kolmogorov complexity
(available as arXiv preprint) | 2018-04-19 | Paper |
Short lists with short programs in short time
Computational Complexity | 2018-04-18 | Paper |
Kolmogorov complexity version of Slepian-Wolf coding
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
On approximate decidability of minimal programs
ACM Transactions on Computation Theory | 2016-10-24 | Paper |
Relative to a random oracle, P/poly is not measurable in EXP
Information Processing Letters | 2016-06-16 | Paper |
Large sets in \(\mathrm{AC}^{0}\) have many strings with low Kolmogorov complexity
Information Processing Letters | 2016-06-01 | Paper |
On optimal language compression for sets in PSPACE/poly
Theory of Computing Systems | 2015-07-20 | Paper |
Short lists with short programs in short time -- a short proof
Language, Life, Limits | 2015-02-25 | Paper |
Counting Dependent and Independent Strings
Fundamenta Informaticae | 2014-05-12 | Paper |
Generating Kolmogorov random strings from sources with limited independence
Journal of Logic and Computation | 2013-08-27 | Paper |
On efficient constructions of short lists containing mostly Ramsey graphs
Lecture Notes in Computer Science | 2013-05-28 | Paper |
Symmetry of Information: A Closer Look
Computation, Physics and Beyond | 2012-06-15 | Paper |
| Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence | 2012-04-24 | Paper |
Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence
(available as arXiv preprint) | 2012-04-24 | Paper |
On the optimal compression of sets in PSPACE
Fundamentals of Computation Theory | 2011-08-19 | Paper |
Counting dependent and independent strings
Mathematical Foundations of Computer Science 2010 | 2010-09-03 | Paper |
Impossibility of independence amplification in Kolmogorov complexity theory
Mathematical Foundations of Computer Science 2010 | 2010-09-03 | Paper |
Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences
Theory of Computing Systems | 2010-08-13 | Paper |
On generating independent random strings
Mathematical Theory and Computational Practice | 2010-07-28 | Paper |
Algorithmically independent sequences
Information and Computation | 2010-04-14 | Paper |
Simple extractors via constructions of cryptographic pseudo-random generators
Theoretical Computer Science | 2010-03-10 | Paper |
LATIN 2004: Theoretical Informatics
Lecture Notes in Computer Science | 2009-05-07 | Paper |
Algorithmically Independent Sequences
Developments in Language Theory | 2008-10-30 | Paper |
Exposure-resilient extractors and the derandomization of probabilistic sublinear time
Computational Complexity | 2008-08-20 | Paper |
Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences
Lecture Notes in Computer Science | 2008-06-05 | Paper |
The complexity of finding top-Toda-equivalence-class members
Theory of Computing Systems | 2006-10-16 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2006-01-10 | Paper |
| scientific article; zbMATH DE number 2133317 (Why is no real title available?) | 2005-02-11 | Paper |
Almost-everywhere superiority for quantum polynomial time
Information and Computation | 2003-01-14 | Paper |
| scientific article; zbMATH DE number 1543340 (Why is no real title available?) | 2001-02-27 | Paper |
| scientific article; zbMATH DE number 1284001 (Why is no real title available?) | 1999-05-03 | Paper |
On the size of classes with weak membership properties
Theoretical Computer Science | 1999-01-12 | Paper |
Weighted NP Optimization Problems: Logical Definability and Approximation Properties
SIAM Journal on Computing | 1998-09-21 | Paper |
Strong self-reducibility precludes strong immunity
Mathematical Systems Theory | 1997-03-03 | Paper |
On the topological size of p-m-complete degrees
Theoretical Computer Science | 1997-02-28 | Paper |
A High-Low Kolmogorov Complexity Law equivalent to the 0-1 Law
Information Processing Letters | 1997-02-28 | Paper |
Effective category and measure in abstract complexity theory
Theoretical Computer Science | 1997-02-28 | Paper |
| scientific article; zbMATH DE number 850635 (Why is no real title available?) | 1996-03-04 | Paper |
| scientific article; zbMATH DE number 782046 (Why is no real title available?) | 1996-02-20 | Paper |
Is independence an exception?
Applied Mathematics and Computation | 1995-05-11 | Paper |
Minimum spanning hypertrees
Discrete Applied Mathematics | 1994-11-28 | Paper |
RECURSIVE BAIRE CLASSIFICATION AND SPEEDABLE FUNCTIONS
Mathematical Logic Quarterly | 1994-06-08 | Paper |
If not empty, NP-P is topologically large
Theoretical Computer Science | 1994-02-17 | Paper |
| scientific article; zbMATH DE number 14489 (Why is no real title available?) | 1992-06-25 | Paper |
| scientific article; zbMATH DE number 4099277 (Why is no real title available?) | 1988-01-01 | Paper |
On relativizations with restricted number of accesses to the oracle set
Mathematical Systems Theory | 1988-01-01 | Paper |
| scientific article; zbMATH DE number 4156420 (Why is no real title available?) | 1987-01-01 | Paper |
On the Topological Size of Sets of Random Strings
Zeitschrift für Mathematische Logik und Grundlagen der Mathematik | 1986-01-01 | Paper |
A relation between correctness and randomness in the computation of probabilistic algorithms
International Journal of Computer Mathematics | 1984-01-01 | Paper |
| scientific article; zbMATH DE number 3870594 (Why is no real title available?) | 1983-01-01 | Paper |
