1 citations · 1 across the 20 of their papers we have counts for
5 papers · 2 filters
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…