4 citations · 6 across the 3 of their papers we have counts for
5 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…
On W[1]-Hardness as Evidence for Intractability
Ralph C. Bottesch
The central conjecture of parameterized complexity states that FPT is not equal to W[1], and is generally regarded as the parameterized counterpart to P != NP. We revisit the issue…
Relativization and Interactive Proof Systems in Parameterized Complexity Theory
Ralph Christian Bottesch
We introduce some classical complexity-theoretic techniques to Parameterized Complexity. First, we study relativization for the machine models that were used by Chen, Flum, and Gro…
Equality, Revisited
Ralph C. Bottesch, Dmytro Gavinsky, Hartmut Klauck
We develop a new lower bound method for analysing the complexity of the Equality function (EQ) in the Simultaneous Message Passing (SMP) model of communication complexity. The new…
Correlation in Hard Distributions in Communication Complexity
Ralph C. Bottesch, Dmitry Gavinsky, Hartmut Klauck
We study the effect that the amount of correlation in a bipartite distribution has on the communication complexity of a problem under that distribution. We introduce a new family o…