Concepedia

Kernelization Lower Bounds

Kernelization Lower Bounds is a theoretical framework in parameterized complexity that establishes limits on the efficiency of kernelization algorithms by proving that certain parameterized problems cannot admit polynomial or smaller kernels unless widely believed complexity-theoretic assumptions fail.

52

Publications

3K

Citations

84

Authors

55

Institutions

Publications per year

2017–2026

11

Parents

Publications

52

Kernelization Lower Bounds by Cross-Composition

Hans L. Bodlaender, Bart Jansen, Stefan Kratsch · SIAM Journal on Discrete Mathematics · 2014 · 230 citations

, , +14

A kernelization algorithm for d-Hitting Set

Faisal N. Abu-Khzam · Journal of Computer and System Sciences · 2009 · 174 citations

, , +7

Kernelization Algorithms for the Vertex Cover Problem: Theory and Experiments.

Faisal N. Abu-Khzam, R. Lorraine Collins, Michael R. Fellows et al. · 2004 · 166 citations

, , +12

Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size

Jianer Chen, Henning Fernau, Iyad Kanj et al. · SIAM Journal on Computing · 2007 · 154 citations

, , +15

Generalization Properties of Learning with Random Features

Alessandro Rudi, Lorenzo Rosasco · CINECA IRIS Institutial Research Information System (University of Genoa) · 2017 · 145 citations · Full text

, , +16

1–5 of 52

Authors

84

  1. SK
    Stefan Kratsch

    Utrecht University, Netherlands

    10 publications · 656 citations

    10

    h-index

  2. SS
    Saket Saurabh

    Institute of Mathematical Sciences, India

    7 publications · 437 citations

    7

    h-index

  3. BM
    Bart M. P. Jansen

    Utrecht University, Netherlands

    6 publications · 229 citations

    6

    h-index

  4. MP
    Marcin Pilipczuk

    University of Warsaw, Poland

    6 publications · 197 citations

    5

    h-index

  5. NM
    Neeldhara Misra

    Indian Institute of Science Bangalore, India

    4 publications · 215 citations

    4

    h-index

1–5 of 84

Institutions

55

  1. Utrecht University

    Utrecht, The Netherlands

    9 h-index

    12 publications

    928 citations

  2. University of Bergen

    Bergen, Norway

    9 h-index

    14 publications

    622 citations

  3. Institute of Mathematical Sciences

    Chennai, India

    8 h-index

    10 publications

    605 citations

  4. University of Warsaw

    Warsaw, Poland

    5 h-index

    16 publications

    569 citations

  5. Max Planck Society

    Munich, Germany

    4 h-index

    7 publications

    592 citations

  6. Eindhoven University of Technology

    Eindhoven, The Netherlands

    3 h-index

    4 publications

    107 citations

  7. Max Planck Institute for Informatics

    Saarbrücken, Germany

    3 h-index

    3 publications

    202 citations

  8. University of Bonn

    Bonn, Germany

    3 h-index

    3 publications

    257 citations

1–8 of 55

Venues

  1. DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

    Repository · 5 publications · 106 citations

    5

    h-index

  2. SIAM Journal on Discrete Mathematics

    4 publications · 375 citations

    4

    h-index

  3. ACM Transactions on Algorithms

    TALG · 4 publications · 247 citations

    4

    h-index

  4. Algorithmica

    3 publications · 40 citations

    3

    h-index

  5. Theoretical Computer Science

    3 publications · 80 citations

    3

    h-index

1–5