We consider the robustness of computational hardness of problems
whose input is obtained by applying independent random deletions to worst-case instances.
For some classical NP-hard problems on graphs, such as Coloring, Vertex-Cover, and Hamiltonicity, we examine the complexity of these problems when edges (or vertices) of an arbitrary
graph are ... more >>>

A natural measure of smoothness of a Boolean function is its sensitivity (the largest number of Hamming neighbors of a point which differ from it in function value). The structure of smooth or equivalently low-sensitivity functions is still a mystery. A well-known conjecture states that every such Boolean function can ... more >>>

We consider several non-uniform variants of parameterized complexity classes that have been considered in the literature. We do so in a homogenous notation, allowing a clear comparison of the various variants. Additionally, we consider some novel (non-uniform) parameterized complexity classes that come up in the framework of parameterized knowledge compilation. ... more >>>