DROPS

Document

Survey

Resilience in Knowledge Graph Embeddings

Authors: Arnab Sharma, N'Dah Jean Kouagou, and Axel-Cyrille Ngonga Ngomo

Published in: TGDK, Volume 3, Issue 2 (2025). Transactions on Graph Data and Knowledge, Volume 3, Issue 2

Abstract

In recent years, knowledge graphs have gained interest and witnessed widespread applications in various domains, such as information retrieval, question-answering, recommendation systems, amongst others. Large-scale knowledge graphs to this end have demonstrated their utility in effectively representing structured knowledge. To further facilitate the application of machine learning techniques, knowledge graph embedding models have been developed. Such models can transform entities and relationships within knowledge graphs into vectors. However, these embedding models often face challenges related to noise, missing information, distribution shift, adversarial attacks, etc. This can lead to sub-optimal embeddings and incorrect inferences, thereby negatively impacting downstream applications. While the existing literature has focused so far on adversarial attacks on KGE models, the challenges related to the other critical aspects remain unexplored. In this paper, we, first of all, give a unified definition of resilience, encompassing several factors such as generalisation, in-distribution generalization, distribution adaption, and robustness. After formalizing these concepts for machine learning in general, we define them in the context of knowledge graphs. To find the gap in the existing works on resilience in the context of knowledge graphs, we perform a systematic survey, taking into account all these aspects mentioned previously. Our survey results show that most of the existing works focus on a specific aspect of resilience, namely robustness. After categorizing such works based on their respective aspects of resilience, we discuss the challenges and future research directions.

Cite as

Arnab Sharma, N'Dah Jean Kouagou, and Axel-Cyrille Ngonga Ngomo. Resilience in Knowledge Graph Embeddings. In Transactions on Graph Data and Knowledge (TGDK), Volume 3, Issue 2, pp. 1:1-1:38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{sharma_et_al:TGDK.3.2.1,
  author =	{Sharma, Arnab and Kouagou, N'Dah Jean and Ngomo, Axel-Cyrille Ngonga},
  title =	{{Resilience in Knowledge Graph Embeddings}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{1:1--1:38},
  ISSN =	{2942-7517},
  year =	{2025},
  volume =	{3},
  number =	{2},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.3.2.1},
  URN =		{urn:nbn:de:0030-drops-248117},
  doi =		{10.4230/TGDK.3.2.1},
  annote =	{Keywords: Knowledge graphs, Resilience, Robustness}
}

Document

DOI: 10.4230/LIPIcs.ITP.2025.23

Formalizing the Hidden Number Problem in Isabelle/HOL

Authors: Sage Binder, Eric Ren, and Katherine Kosaian

Published in: LIPIcs, Volume 352, 16th International Conference on Interactive Theorem Proving (ITP 2025)

Abstract

We formalize the hidden number problem (HNP), as introduced in a seminal work by Boneh and Venkatesan in 1996, in Isabelle/HOL. Intuitively, the HNP involves demonstrating the existence of an algorithm (the "adversary") which can compute (with high probability) a hidden number α given access to a bit-leaking oracle. Originally developed to establish the security of Diffie-Hellman key exchange, the HNP has since been used not only for protocol security but also in cryptographic attacks, including notable ones on DSA and ECDSA. Further, as the HNP establishes an expressive paradigm for reasoning about security in the context of information leakage, many HNP variants for other specialized cryptographic applications have since been developed. A main contribution of our work is explicating and clarifying the HNP proof blueprint from the original source material; naturally, formalization forces us to make all assumptions and proof steps precise and transparent. For example, the source material did not explicitly define the adversary and only abstractly defined what information is being leaked; our formalization concretizes both definitions. Additionally, the HNP makes use of an instance of Babai’s nearest plane algorithm, which solves the approximate closest vector problem; we formalize this as a result of independent interest. Our formalizations of Babai’s algorithm and the HNP adversary are executable, setting up potential future work, e.g. in developing formally verified instances of cryptographic attacks.

Cite as

Sage Binder, Eric Ren, and Katherine Kosaian. Formalizing the Hidden Number Problem in Isabelle/HOL. In 16th International Conference on Interactive Theorem Proving (ITP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 352, pp. 23:1-23:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{binder_et_al:LIPIcs.ITP.2025.23,
  author =	{Binder, Sage and Ren, Eric and Kosaian, Katherine},
  title =	{{Formalizing the Hidden Number Problem in Isabelle/HOL}},
  booktitle =	{16th International Conference on Interactive Theorem Proving (ITP 2025)},
  pages =	{23:1--23:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-396-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{352},
  editor =	{Forster, Yannick and Keller, Chantal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2025.23},
  URN =		{urn:nbn:de:0030-drops-246216},
  doi =		{10.4230/LIPIcs.ITP.2025.23},
  annote =	{Keywords: hidden number problem, Babai’s nearest plane algorithm, cryptography, interactive theorem proving, Isabelle/HOL}
}

Document

DOI: 10.4230/LIPIcs.WABI.2025.11

Mutational Signature Refitting on Sparse Pan-Cancer Data

Authors: Gal Gilad, Teresa M. Przytycka, and Roded Sharan

Published in: LIPIcs, Volume 344, 25th International Conference on Algorithms for Bioinformatics (WABI 2025)

Abstract

Mutational processes shape cancer genomes, leaving characteristic marks that are termed signatures. The level of activity of each such process, or its signature exposure, provides important information on the disease, improving patient stratification and the prediction of drug response. Thus, there is growing interest in developing refitting methods that decipher those exposures. Previous work in this domain was unsupervised in nature, employing algebraic decomposition and probabilistic inference methods. Here we provide a supervised approach to the problem of signature refitting and show its superiority over current methods. Our method, SuRe, leverages a neural network model to capture correlations between signature exposures in real data. We show that SuRe outperforms previous methods on sparse mutation data from tumor type specific data sets, as well as pan-cancer data sets, with an increasing advantage as the data become sparser. We further demonstrate its utility in clinical settings.

Cite as

Gal Gilad, Teresa M. Przytycka, and Roded Sharan. Mutational Signature Refitting on Sparse Pan-Cancer Data. In 25th International Conference on Algorithms for Bioinformatics (WABI 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 344, pp. 11:1-11:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gilad_et_al:LIPIcs.WABI.2025.11,
  author =	{Gilad, Gal and Przytycka, Teresa M. and Sharan, Roded},
  title =	{{Mutational Signature Refitting on Sparse Pan-Cancer Data}},
  booktitle =	{25th International Conference on Algorithms for Bioinformatics (WABI 2025)},
  pages =	{11:1--11:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-386-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{344},
  editor =	{Brejov\'{a}, Bro\v{n}a and Patro, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2025.11},
  URN =		{urn:nbn:de:0030-drops-239374},
  doi =		{10.4230/LIPIcs.WABI.2025.11},
  annote =	{Keywords: mutational signatures, signature refitting, cancer genomics, genomic data analysis, somatic mutations}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2025.66

Graph Reconstruction via MIS Queries

Authors: Christian Konrad, Conor O'Sullivan, and Victor Traistaru

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract

In the Graph Reconstruction (GR) problem, a player initially only knows the vertex set V of an input graph G = (V, E) and is required to learn its set of edges E. To this end, the player submits queries to an oracle and must deduce E from the oracle’s answers. Angluin and Chen [Journal of Computer and System Sciences, 2008] resolved the number of Independent Set (IS) queries necessary and sufficient for GR on m-edge graphs. In this setting, each query consists of a subset of vertices U ⊆ V, and the oracle responds with a boolean, indicating whether U is an independent set in G. They gave algorithms that use O(m ⋅ log n) IS queries, which is best possible. In this paper, we initiate the study of GR via Maximal Independent Set (MIS) queries, a more powerful variant of IS queries. Given a query U ⊆ V, the oracle responds with any, potentially adversarially chosen, maximal independent set I ⊆ U in the induced subgraph G[U]. We show that, for GR, MIS queries are strictly more powerful than IS queries when parametrized by the maximum degree Δ of the input graph. We give tight (up to poly-logarithmic factors) upper and lower bounds for this problem: 1) We observe that the simple strategy of taking uniform independent random samples of V and submitting those to the oracle yields a non-adaptive randomized algorithm that executes O(Δ² ⋅ log n) queries and succeeds with high probability. This should be contrasted with the fact that Ω(Δ ⋅ n ⋅ log(n/Δ)) IS queries are required for such graphs, which shows that MIS queries are strictly more powerful than IS queries. Interestingly, combining the strategy of taking uniform random samples of V with the probabilistic method, we show the existence of a deterministic non-adaptive algorithm that executes O(Δ³ ⋅ log(n/Δ)) queries. 2) Regarding lower bounds, we prove that the additional Δ factor when going from randomized non-adaptive algorithms to deterministic non-adaptive algorithms is necessary. We show that every non-adaptive deterministic algorithm requires Ω(Δ³ / log² Δ) queries. For arbitrary randomized adaptive algorithms, we show that Ω(Δ²) queries are necessary in graphs of maximum degree Δ, and that Ω(log n) queries are necessary, even when the input graph is an n-vertex cycle.

Cite as

Christian Konrad, Conor O'Sullivan, and Victor Traistaru. Graph Reconstruction via MIS Queries. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 66:1-66:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{konrad_et_al:LIPIcs.ITCS.2025.66,
  author =	{Konrad, Christian and O'Sullivan, Conor and Traistaru, Victor},
  title =	{{Graph Reconstruction via MIS Queries}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{66:1--66:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.66},
  URN =		{urn:nbn:de:0030-drops-226945},
  doi =		{10.4230/LIPIcs.ITCS.2025.66},
  annote =	{Keywords: Query Complexity, Graph Reconstruction, Maximal Independent Set Queries}
}

Document

DOI: 10.4230/DagRep.3.8.1

Reinforcement Learning (Dagstuhl Seminar 13321)

Authors: Peter Auer, Marcus Hutter, and Laurent Orseau

Published in: Dagstuhl Reports, Volume 3, Issue 8 (2013)

Abstract

This Dagstuhl Seminar also stood as the 11th European Workshop on Reinforcement Learning (EWRL11). Reinforcement learning gains more and more attention each year, as can be seen at the various conferences (ECML, ICML, IJCAI, ...). EWRL, and in particular this Dagstuhl Seminar, aimed at gathering people interested in reinforcement learning from all around the globe. This unusual format for EWRL helped viewing the field and discussing topics differently.

Cite as

Peter Auer, Marcus Hutter, and Laurent Orseau. Reinforcement Learning (Dagstuhl Seminar 13321). In Dagstuhl Reports, Volume 3, Issue 8, pp. 1-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{auer_et_al:DagRep.3.8.1,
  author =	{Auer, Peter and Hutter, Marcus and Orseau, Laurent},
  title =	{{Reinforcement Learning (Dagstuhl Seminar 13321)}},
  pages =	{1--26},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{8},
  editor =	{Auer, Peter and Hutter, Marcus and Orseau, Laurent},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.8.1},
  URN =		{urn:nbn:de:0030-drops-43409},
  doi =		{10.4230/DagRep.3.8.1},
  annote =	{Keywords: Machine Learning, Reinforcement Learning, Markov Decision Processes, Planning}
}

Document

DOI: 10.4230/DagSemProc.06201.6

Sequence prediction for non-stationary processes

Authors: Daniil Ryabko and Marcus Hutter

Published in: Dagstuhl Seminar Proceedings, Volume 6201, Combinatorial and Algorithmic Foundations of Pattern and Association Discovery (2006)

Abstract

We address the problem of sequence prediction for nonstationary stochastic processes. In particular, given two measures on the set of one-way infinite sequences over a finite alphabet, consider the question whether one of the measures predicts the other. We find some conditions on local absolute continuity under which prediction is possible.

Cite as

Daniil Ryabko and Marcus Hutter. Sequence prediction for non-stationary processes. In Combinatorial and Algorithmic Foundations of Pattern and Association Discovery. Dagstuhl Seminar Proceedings, Volume 6201, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{ryabko_et_al:DagSemProc.06201.6,
  author =	{Ryabko, Daniil and Hutter, Marcus},
  title =	{{Sequence prediction for non-stationary processes}},
  booktitle =	{Combinatorial and Algorithmic Foundations of Pattern and Association Discovery},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6201},
  editor =	{Rudolf Ahlswede and Alberto Apostolico and Vladimir I. Levenshtein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06201.6},
  URN =		{urn:nbn:de:0030-drops-7900},
  doi =		{10.4230/DagSemProc.06201.6},
  annote =	{Keywords: Sequence prediction, probability forecasting, local absolute continuity}
}

Document

DOI: 10.4230/DagSemProc.06051.1

06051 Abstracts Collection – Kolmogorov Complexity and Applications

Authors: Marcus Hutter, Wolfgang Merkle, and Paul M.B. Vitanyi

Published in: Dagstuhl Seminar Proceedings, Volume 6051, Kolmogorov Complexity and Applications (2006)

Abstract

From 29.01.06 to 03.02.06, the Dagstuhl Seminar 06051 ``Kolmogorov Complexity and Applications'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Marcus Hutter, Wolfgang Merkle, and Paul M.B. Vitanyi. 06051 Abstracts Collection – Kolmogorov Complexity and Applications. In Kolmogorov Complexity and Applications. Dagstuhl Seminar Proceedings, Volume 6051, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{hutter_et_al:DagSemProc.06051.1,
  author =	{Hutter, Marcus and Merkle, Wolfgang and Vitanyi, Paul M.B.},
  title =	{{06051 Abstracts Collection – Kolmogorov Complexity and Applications}},
  booktitle =	{Kolmogorov Complexity and Applications},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6051},
  editor =	{Marcus Hutter and Wolfgang Merkle and Paul M.B. Vitanyi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06051.1},
  URN =		{urn:nbn:de:0030-drops-6632},
  doi =		{10.4230/DagSemProc.06051.1},
  annote =	{Keywords: Information theory, Kolmogorov Complexity, effective randomnes, algorithmic probability, recursion theory, computational complexity, machine learning knowledge discovery}
}

Document

DOI: 10.4230/DagSemProc.06051.2

Application of Kolmogorov complexity and universal codes to identity testing and nonparametric testing of serial independence for time series.

Authors: Boris Ryabko, Jaakko Astola, and Alex Gammerman

Published in: Dagstuhl Seminar Proceedings, Volume 6051, Kolmogorov Complexity and Applications (2006)

Abstract

We show that Kolmogorov complexity and such its estimators as universal codes (or data compression methods) can be applied for hypothesis testing in a framework of classical mathematical statistics. The methods for identity testing and nonparametric testing of serial independence for time series are described.

Cite as

Boris Ryabko, Jaakko Astola, and Alex Gammerman. Application of Kolmogorov complexity and universal codes to identity testing and nonparametric testing of serial independence for time series.. In Kolmogorov Complexity and Applications. Dagstuhl Seminar Proceedings, Volume 6051, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{ryabko_et_al:DagSemProc.06051.2,
  author =	{Ryabko, Boris and Astola, Jaakko and Gammerman, Alex},
  title =	{{Application of Kolmogorov complexity and universal codes to identity testing and nonparametric testing of serial independence for time series.}},
  booktitle =	{Kolmogorov Complexity and Applications},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6051},
  editor =	{Marcus Hutter and Wolfgang Merkle and Paul M.B. Vitanyi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06051.2},
  URN =		{urn:nbn:de:0030-drops-6363},
  doi =		{10.4230/DagSemProc.06051.2},
  annote =	{Keywords: Algorithmic complexity, algorithmic information theory, Kolmogorov complexity, universal coding, hypothesis testing}
}

Document

DOI: 10.4230/DagSemProc.06051.3

Automatic Meaning Discovery Using Google

Authors: Rudi Cilibrasi and Paul M.B. Vitanyi

Published in: Dagstuhl Seminar Proceedings, Volume 6051, Kolmogorov Complexity and Applications (2006)

Abstract

We survey a new area of parameter-free similarity distance measures useful in data-mining, pattern recognition, learning and automatic semantics extraction. Given a family of distances on a set of objects, a distance is universal up to a certain precision for that family if it minorizes every distance in the family between every two objects in the set, up to the stated precision (we do not require the universal distance to be an element of the family). We consider similarity distances for two types of objects: literal objects that as such contain all of their meaning, like genomes or books, and names for objects. The latter may have literal embodyments like the first type, but may also be abstract like ``red'' or ``christianity.'' For the first type we consider a family of computable distance measures corresponding to parameters expressing similarity according to particular features between pairs of literal objects. For the second type we consider similarity distances generated by web users corresponding to particular semantic relations between the (names for) the designated objects. For both families we give universal similarity distance measures, incorporating all particular distance measures in the family. In the first case the universal distance is based on compression and in the second case it is based on Google page counts related to search terms. In both cases experiments on a massive scale give evidence of the viability of the approaches.

Cite as

Rudi Cilibrasi and Paul M.B. Vitanyi. Automatic Meaning Discovery Using Google. In Kolmogorov Complexity and Applications. Dagstuhl Seminar Proceedings, Volume 6051, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{cilibrasi_et_al:DagSemProc.06051.3,
  author =	{Cilibrasi, Rudi and Vitanyi, Paul M.B.},
  title =	{{Automatic Meaning Discovery Using Google}},
  booktitle =	{Kolmogorov Complexity and Applications},
  pages =	{1--23},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6051},
  editor =	{Marcus Hutter and Wolfgang Merkle and Paul M.B. Vitanyi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06051.3},
  URN =		{urn:nbn:de:0030-drops-6296},
  doi =		{10.4230/DagSemProc.06051.3},
  annote =	{Keywords: Normalized Compression Distance, Clustering, Clasification, Relative Semantics of Terms, Google, World-Wide-Web, Kolmogorov complexity}
}

Document

DOI: 10.4230/DagSemProc.06051.4

Binary Lambda Calculus and Combinatory Logic

Authors: John Tromp

Published in: Dagstuhl Seminar Proceedings, Volume 6051, Kolmogorov Complexity and Applications (2006)

Abstract

We introduce binary representations of both lambda calculus and combinatory logic terms, and demonstrate their simplicity by providing very compact parser-interpreters for these binary languages. We demonstrate their application to Algorithmic Information Theory with several concrete upper bounds on program-size complexity, including an elegant self-delimiting code for binary strings.

Cite as

John Tromp. Binary Lambda Calculus and Combinatory Logic. In Kolmogorov Complexity and Applications. Dagstuhl Seminar Proceedings, Volume 6051, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{tromp:DagSemProc.06051.4,
  author =	{Tromp, John},
  title =	{{Binary Lambda Calculus and Combinatory Logic}},
  booktitle =	{Kolmogorov Complexity and Applications},
  pages =	{1--20},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6051},
  editor =	{Marcus Hutter and Wolfgang Merkle and Paul M.B. Vitanyi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06051.4},
  URN =		{urn:nbn:de:0030-drops-6289},
  doi =		{10.4230/DagSemProc.06051.4},
  annote =	{Keywords: Concrete, program size complexity, ambda calculus, combinatory logic, encoding, self-delimiting, binary strings}
}

Document

DOI: 10.4230/DagSemProc.06051.5

Combinatorial proof of Muchnik's theorem

Authors: Alexander Shen

Published in: Dagstuhl Seminar Proceedings, Volume 6051, Kolmogorov Complexity and Applications (2006)

Abstract

Original proof of Muchnik's theorem on conditional descriptions can be modified and split into two parts: 1) we construct a graph that allows large online matchings (main part) 2) we use this graph to prove the theorem The question about online matching could be interesting in itself.

Cite as

Alexander Shen. Combinatorial proof of Muchnik's theorem. In Kolmogorov Complexity and Applications. Dagstuhl Seminar Proceedings, Volume 6051, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{shen:DagSemProc.06051.5,
  author =	{Shen, Alexander},
  title =	{{Combinatorial proof of Muchnik's theorem}},
  booktitle =	{Kolmogorov Complexity and Applications},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6051},
  editor =	{Marcus Hutter and Wolfgang Merkle and Paul M.B. Vitanyi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06051.5},
  URN =		{urn:nbn:de:0030-drops-6258},
  doi =		{10.4230/DagSemProc.06051.5},
  annote =	{Keywords: Matching conditional descriptions Kolmogorov complexity}
}

Document

DOI: 10.4230/DagSemProc.06051.6

Complexity Monotone in Conditions and Future Prediction Errors

Authors: Alexey Chernov, Marcus Hutter, and Jürgen Schmidhuber

Published in: Dagstuhl Seminar Proceedings, Volume 6051, Kolmogorov Complexity and Applications (2006)

Abstract

We bound the future loss when predicting any (computably) stochastic sequence online. Solomonoff finitely bounded the total deviation of his universal predictor $M$ from the true distribution $mu$ by the algorithmic complexity of $mu$. Here we assume we are at a time $t>1$ and already observed $x=x_1...x_t$. We bound the future prediction performance on $x_{t+1}x_{t+2}...$ by a new variant of algorithmic complexity of $mu$ given $x$, plus the complexity of the randomness deficiency of $x$. The new complexity is monotone in its condition in the sense that this complexity can only decrease if the condition is prolonged. We also briefly discuss potential generalizations to Bayesian model classes and to classification problems.

Cite as

Alexey Chernov, Marcus Hutter, and Jürgen Schmidhuber. Complexity Monotone in Conditions and Future Prediction Errors. In Kolmogorov Complexity and Applications. Dagstuhl Seminar Proceedings, Volume 6051, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{chernov_et_al:DagSemProc.06051.6,
  author =	{Chernov, Alexey and Hutter, Marcus and Schmidhuber, J\"{u}rgen},
  title =	{{Complexity Monotone in Conditions and Future Prediction Errors}},
  booktitle =	{Kolmogorov Complexity and Applications},
  pages =	{1--20},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6051},
  editor =	{Marcus Hutter and Wolfgang Merkle and Paul M.B. Vitanyi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06051.6},
  URN =		{urn:nbn:de:0030-drops-6327},
  doi =		{10.4230/DagSemProc.06051.6},
  annote =	{Keywords: Kolmogorov complexity, posterior bounds, online sequential prediction, Solomonoff prior, monotone conditional complexity, total error, future loss, ra}
}

Document

DOI: 10.4230/DagSemProc.06051.7

Error in Enumerable Sequence Prediction

Authors: Nick Hay

Published in: Dagstuhl Seminar Proceedings, Volume 6051, Kolmogorov Complexity and Applications (2006)

Abstract

We outline a method for quantifying the error of a sequence prediction. With sequence predictions represented by semimeasures $ u(x)$ we define their error to be $-log_2 u(x)$. We note that enumerable semimeasures are those which model the sequence as the output of a computable system given unknown input. Using this we define the simulation complexity of a computable system $C$ relative to another $U$ giving an emph{exact} bound on their difference in error. This error in turn gives an exact upper bound on the number of predictions $ u$ gets incorrect.

Cite as

Nick Hay. Error in Enumerable Sequence Prediction. In Kolmogorov Complexity and Applications. Dagstuhl Seminar Proceedings, Volume 6051, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{hay:DagSemProc.06051.7,
  author =	{Hay, Nick},
  title =	{{Error in Enumerable Sequence Prediction}},
  booktitle =	{Kolmogorov Complexity and Applications},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6051},
  editor =	{Marcus Hutter and Wolfgang Merkle and Paul M.B. Vitanyi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06051.7},
  URN =		{urn:nbn:de:0030-drops-6331},
  doi =		{10.4230/DagSemProc.06051.7},
  annote =	{Keywords: Sequence prediction, Solomonoff induction, enumerable semimeasures}
}

Document

DOI: 10.4230/DagSemProc.06051.8

Learning in Reactive Environments with Arbitrary Dependence

Authors: Daniil Ryabko and Marcus Hutter

Published in: Dagstuhl Seminar Proceedings, Volume 6051, Kolmogorov Complexity and Applications (2006)

Abstract

In reinforcement learning the task for an agent is to attain the best possible asymptotic reward where the true generating environment is unknown but belongs to a known countable family of environments. This task generalises the sequence prediction problem, in which the environment does not react to the behaviour of the agent. Solomonoff induction solves the sequence prediction problem for any countable class of measures; however, it is easy to see that such result is impossible for reinforcement learning - not any countable class of environments can be learnt. We find some sufficient conditions on the class of environments under which an agent exists which attains the best asymptotic reward for any environment in the class. We analyze how tight these conditions are and how they relate to different probabilistic assumptions known in reinforcement learning and related fields, such as Markov Decision Processes and mixing conditions.

Cite as

Daniil Ryabko and Marcus Hutter. Learning in Reactive Environments with Arbitrary Dependence. In Kolmogorov Complexity and Applications. Dagstuhl Seminar Proceedings, Volume 6051, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{ryabko_et_al:DagSemProc.06051.8,
  author =	{Ryabko, Daniil and Hutter, Marcus},
  title =	{{Learning in  Reactive Environments with Arbitrary Dependence}},
  booktitle =	{Kolmogorov Complexity and Applications},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6051},
  editor =	{Marcus Hutter and Wolfgang Merkle and Paul M.B. Vitanyi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06051.8},
  URN =		{urn:nbn:de:0030-drops-6372},
  doi =		{10.4230/DagSemProc.06051.8},
  annote =	{Keywords: Reinforcement learning, asymptotic average value, self-optimizing policies, (non) Markov decision processes}
}

Document

DOI: 10.4230/DagSemProc.06051.9

Multisource Algorithmic Information Theory

Authors: Alexander Shen

Published in: Dagstuhl Seminar Proceedings, Volume 6051, Kolmogorov Complexity and Applications (2006)

Abstract

Multisource information theory is well known in Shannon setting. It studies the possibilities of information transfer through a network with limited capacities. Similar questions could be studied for algorithmic information theory and provide a framework for several known results and interesting questions.

Cite as

Alexander Shen. Multisource Algorithmic Information Theory. In Kolmogorov Complexity and Applications. Dagstuhl Seminar Proceedings, Volume 6051, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{shen:DagSemProc.06051.9,
  author =	{Shen, Alexander},
  title =	{{Multisource Algorithmic Information Theory}},
  booktitle =	{Kolmogorov Complexity and Applications},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6051},
  editor =	{Marcus Hutter and Wolfgang Merkle and Paul M.B. Vitanyi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06051.9},
  URN =		{urn:nbn:de:0030-drops-6267},
  doi =		{10.4230/DagSemProc.06051.9},
  annote =	{Keywords: Kolmogorov complexity multisource information theory}
}

18 Search Results for "Hutter, Marcus"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message