6 citations · 16 across the 7 of their papers we have counts for
4 papers · 1 filter
A Hierarchy of Polynomial Kernels
Jouke Witteveen, Ralph Bottesch, Leen Torenvliet
In parameterized algorithmics, the process of kernelization is defined as a polynomial time algorithm that transforms the instance of a given problem to an equivalent instance of a…
Normalized Information Distance is Not Semicomputable
Sebastiaan A. Terwijn, Leen Torenvliet, Paul M. B. Vitanyi
Normalized information distance (NID) uses the theoretical notion of Kolmogorov complexity, which for practical purposes is approximated by the length of the compressed version of…
Nonapproximablity of the Normalized Information Distance
Sebastiaan A. Terwijn, Leen Torenvliet, Paul M. B. Vitanyi
Normalized information distance (NID) uses the theoretical notion of Kolmogorov complexity, which for practical purposes is approximated by the length of the compressed version of…
P-Selectivity, Immunity, and the Power of One Bit
Lane A. Hemaspaandra, Leen Torenvliet
We prove that P-sel, the class of all P-selective sets, is EXP-immune, but is not EXP/1-immune. That is, we prove that some infinite P-selective set has no infinite EXP-time subset…