Compression of enumerations and gain
We study the compressibility of enumerations in the context of Kolmogorov complexity, focusing on strong and weak forms of compression and their gain: the amount of auxiliary information embedded in the compressed enumeration. The existence of strong compression and weak gainless compression is shown for any computably enumerable (c.e.) set. The density problem of c.e. sets with respect to their prefix complexity is reduced to the question of whether every c.e. set is well-compressible, which we study via enumeration games.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Some enumerations of binary digital images
The topology of digital images has been studied much in recent years, but no attempt has been made to exhaustively catalog the structure of binary images of small numbers of points. We produce enumerations of several cla…
Towards automation of threat modeling based on a semantic model of attack patterns and weaknesses
This works considers challenges of building and usage a formal knowledge base (model), which unites the ATT&CK, CAPEC, CWE, CVE security enumerations. The proposed model can be used to learn relations between attack tech…
LEA: Label Enumeration Attack in Vertical Federated Learning
A typical Vertical Federated Learning (VFL) scenario involves several participants collaboratively training a machine learning model, where each party has different features for the same samples, with labels held exclusi…
Federated LearningPAC Learning, VC Dimension, and the Arithmetic Hierarchy
We compute that the index set of PAC-learnable concept classes is $m$-complete $\Sigma^0_3$ within the set of indices for all concept classes of a reasonable form. All concept classes considered are computable enumeratio…
AllPAC learningLattice Paths for Persistent Diagrams
Persistent homology has undergone significant development in recent years. However, one outstanding challenge is to build a coherent statistical inference procedure on persistent diagrams. In this paper, we first present…
Topological Data Analysis