6 citations · 26 across the 32 of their papers we have counts for
9 papers · 1 filter
Learning Finite-Memory Binary Sources
Maciej Skorski
Estimating biased finite-memory sources from a single trajectory is a fundamental problem with practical impact, for example in estimating entropy for cryptography. We study order-…
On Missing Mass Variance
Maciej Skorski
The missing mass refers to the probability of elements not observed in a sample, and since the work of Good and Turing during WWII, has been studied extensively in many areas inclu…
Concentration Bounds for the Collision Estimator
Maciej Skorski
We prove a strong concentration result about the natural collision estimator, which counts the number of collisions that occur within an iid sample. This estimator is at the heart…
Analytic Formulas for Renyi Entropy of Hidden Markov Models
Joachim Breitner, Maciej Skorski
Determining entropy rates of stochastic processes is a fundamental and difficult problem, with closed-form solutions known only for specific cases. This paper pushes the state-of-t…
Entropy of Independent Experiments, Revisited
Maciej Skorski
The weak law of large numbers implies that, under mild assumptions on the source, the Renyi entropy per produced symbol converges (in probability) towards the Shannon entropy rate.…
Strong Chain Rules for Min-Entropy under Few Bits Spoiled
Maciej Skorski
It is well established that the notion of min-entropy fails to satisfy the \emph{chain rule} of the form , known for Shannon Entropy. Such a property would he…
On the Complexity of Estimating Renyi Divergences
Maciej Skorski
This paper studies the complexity of estimating Renyi divergences of discrete distributions: observed from samples and the baseline distribution known \emph{a priori}. Exte…
A Convex Analysis Approach to Computational Entropy
Maciej Skórski
This paper studies the notion of computational entropy. Using techniques from convex optimization, we investigate the following problems: (a) Can we derandomize the computational e…
Modulus Computational Entropy
Maciej Skorski
The so-called {\em leakage-chain rule} is a very important tool used in many security proofs. It gives an upper bound on the entropy loss of a random variable in case the adver…