Bruno Bauwens

J. ACM, April, 2023

2022

Hall-type theorems for fast almost dynamic matching and applications.

[BibT_eX]

[DOI]

CoRR, 2022

Inequalities for space-bounded Kolmogorov complexity.

[BibT_eX]

[DOI]

Péter Gács

Andrei E. Romashchenko

Comput., 2022

2020

Uniform van Lambalgen's theorem fails for computable randomness.

[BibT_eX]

[DOI]

Inf. Comput., 2020

Precise Expression for the Algorithmic Information Distance.

[BibT_eX]

[DOI]

CoRR, 2020

Universal codes in the shared-randomness model for channels with general distortion capabilities.

[BibT_eX]

[DOI]

CoRR, 2020

Information Distance Revisited.

[BibT_eX]

[DOI]

Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

The Normalized Algorithmic Information Distance Can Not Be Approximated.

[BibT_eX]

[DOI]

Ilya Blinnikov

Proceedings of the Computer Science - Theory and Applications, 2020

2018

Information Distance Revisited.

[BibT_eX]

[DOI]

CoRR, 2018

Optimal probabilistic polynomial time compression and the Slepian-Wolf theorem: tighter version and simple proofs.

[BibT_eX]

[DOI]

CoRR, 2018

Short lists with short programs in short time.

[BibT_eX]

[DOI]

Anton Makhlin

Nikolai K. Vereshchagin

Comput. Complex., 2018

LZW-Kernel: fast kernel utilizing variable length code blocks from LZW compressors for protein sequence classification.

[BibT_eX]

[DOI]

Gleb Filatov

Attila Kertész-Farkas

Bioinform., 2018

2017

Conditional Probabilities and van Lambalgen's Theorem Revisited.

[BibT_eX]

[DOI]

Hayato Takahashi

Theory Comput. Syst., 2017

Conditional Measure and the Violation of Van Lambalgen's Theorem for Martin-Löf Randomness.

[BibT_eX]

[DOI]

Luis Filipe Coelho Antunes

Theory Comput. Syst., 2017

Sophistication vs Logical Depth.

[BibT_eX]

[DOI]

André Souto

Andreia Teixeira

Theory Comput. Syst., 2017

2016

Relating and Contrasting Plain and Prefix Kolmogorov Complexity.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2016

2015

Linear list-approximation for short programs (or the power of a few random bits).

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs.

[BibT_eX]

[DOI]

Arch. Math. Log., 2015

2014

Complexity of Complexity and Strings with Maximal Plain and Prefix Kolmogorov Complexity.

[BibT_eX]

[DOI]

J. Symb. Log., 2014

Asymmetry of the Kolmogorov complexity of online predicting odd and even bits.

[BibT_eX]

[DOI]

Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

2013

An Additivity Theorem for Plain Kolmogorov Complexity.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2013

Upper semicomputable sumtests for lower semicomputable semimeasures.

[BibT_eX]

[DOI]

CoRR, 2013

2012

Complexity of Complexity and Maximal Plain versus Prefix-Free Kolmogorov Complexity.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

Notes on Sum-Tests and Independence Tests.

[BibT_eX]

[DOI]

Sebastiaan A. Terwijn

Theory Comput. Syst., 2011

An additivity theorem for plain complexity

[BibT_eX]

[DOI]

CoRR, 2011

2010

m-sophistication

[BibT_eX]

[DOI]

CoRR, 2010

Directional predictions for 4-class BCI data.

[BibT_eX]

[DOI]

Proceedings of the 18th European Symposium on Artificial Neural Networks, 2010

2009

On the equivalence between minimal sufficient statistics, minimal typical models and initial segments of the Halting sequence

[BibT_eX]

[DOI]

CoRR, 2009

Additivity of on-line decision complexity is violated by a linear term in the length of a binary string

[BibT_eX]

[DOI]