1 citations · 1 across the 20 of their papers we have counts for
22 papers
Regression and Algorithmic Information Theory
Samuel Epstein
In this paper we prove a theorem about regression, in that the shortest description of a function consistent with a finite sample of data is less than the combined conditional Kolm…
A Quantum Outlier Theorem
Samuel Epstein
In recent results, it has been proven that all sampling methods produce outliers. In this paper, we extend these results to quantum information theory. Projectors of large rank mus…
On the Algorithmic Information Between Probabilities
Samuel Epstein
We extend algorithmic conservation inequalities to probability measures. The amount of self information of a probability measure cannot increase when submitted to randomized proces…
Uniform Tests and Algorithmic Thermodynamic Entropy
Samuel Epstein
We prove that given a computable metric space and two computable measures, the set of points that have high universal uniform test scores with respect to the first measure will hav…
How to Compress the Solution
Samuel Epstein
Using derandomization, we provide an upper bound on the compression size of solutions to the graph coloring problem. In general, if solutions to a combinatorial problem exist with…
On the Existence of Anomalies, The Reals Case
Samuel Epstein
The Independence Postulate (IP) is a finitary Church-Turing Thesis, saying mathematical sequences are independent from physical ones. Modelling observations as infinite sequences o…
On the Existence of Anomalies
Samuel Epstein
The Independence Postulate (IP) is a finitary Church-Turing Thesis, saying mathematical sequences are independent from physical ones. IP implies the existence of anomalies.
Some Implications of the Independence Postulate for Physics
Samuel Epstein
The Many Worlds Theory and Constructor Theory are in conflict with the Independence Postulate. The conflict with the Many Worlds Theory is shown through the existence of a finite e…
A Quantum EL Theorem
Samuel Epstein
In this paper, we prove a quantum version of the EL Theorem. It states that non-exotic projections of large rank must have simple quantum states in their images. A consequence to t…
Derandomization under Different Resource Constraints
Samuel Epstein
We provide another proof to the EL Theorem. We show the tradeoff between compressibility of codebooks and their communication capacity. A resource bounded version of the EL Theorem…
22 Examples of Solution Compression via Derandomization
Samuel Epstein
We provide bounds on the compression size of the solutions to 22 problems in computer science. For each problem, we show that solutions exist with high probability, for some simple…
The Kolmogorov Birthday Paradox
Samuel Epstein
We prove a Kolmogorov complexity variant of the birthday paradox. Sufficiently sized random subsets of strings are guaranteed to have two members x and y with low K(x/y). To prove…
The Outlier Theorem Revisited
Samuel Epstein
An outlier is a datapoint that is set apart from a sample population. The outlier theorem in algorithmic information theory states that given a computable sampling method, outliers…
On the Kolmogorov Complexity of Binary Classifiers
Samuel Epstein
We provide tight upper and lower bounds on the expected minimum Kolmogorov complexity of binary classifiers that are consistent with labeled samples. The expected size is not more…
On the Algorithmic Content of Quantum Measurements
Samuel Epstein
We show that given a quantum measurement, for an overwhelming majority of pure states, no meaningful information is produced. This is independent of the number of outcomes of the q…
Extending Chaitin's Incompleteness Theorem
Samuel Epstein
Chaitin's incompleteness theorem states that sufficiently rich formal systems cannot prove lower bounds on Kolmogorov complexity. In this paper we extend this theorem by showing th…
The EL Theorem
Samuel Epstein
The combined universal probability of strings in sets is close to max over in : their logs differ by at most 's information $\math…
On the Conditional Complexity of Sets of Strings
Samuel Epstein
Given a set X of finite strings, one interesting question to ask is whether there exists a member of X which is simple conditional to all other members of X. Conditional simplicity…
Algorithmic No-Cloning Theorem
Samuel Epstein
We introduce the notions of algorithmic mutual information and rarity of quantum states. These definitions enjoy conservation inequalities over unitary transformations and partial…
An Extended Coding Theorem with Application to Quantum Complexities
Samuel Epstein
This paper introduces a new inequality in algorithmic information theory that can be seen as an extended coding theorem. This inequality has applications in new bounds between quan…
Randomness Conservation over Algorithms
Samuel Epstein
Current discrete randomness and information conservation inequalities are over total recursive functions, i.e. restricted to deterministic processing. This restriction implies that…
All Sampling Methods Produce Outliers
Samuel Epstein
Given a computable probability measure P over natural numbers or infinite binary sequences, there is no computable, randomized method that can produce an arbitrarily large sample s…