6 citations · 16 across the 7 of their papers we have counts for
7 papers
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…
Levelable Sets and the Algebraic Structure of Parameterizations
Jouke Witteveen, Leen Torenvliet
Asking which sets are fixed-parameter tractable for a given parameterization constitutes much of the current research in parameterized complexity theory. This approach faces some o…
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…
Separating complexity classes using autoreducibility
Harry Buhrman, Lance Fortnow, Leen Torenvliet +1
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hie…
A Note on the Complexity of Restricted Attribute-Value Grammars
Leen Torenvliet, Marten Trautwein
The recognition problem for attribute-value grammars (AVGs) was shown to be undecidable by Johnson in 1988. Therefore, the general form of AVGs is of no practical use. In this pape…