6 citations · 12 across the 15 of their papers we have counts for
4 papers · 1 filter
Diminishable Parameterized Problems and Strict Polynomial Kernelization
Henning Fernau, Till Fluschnik, Danny Hermelin +3
Kernelization---a mathematical key concept for provably effective polynomial-time preprocessing of NP-hard problems---plays a central role in parameterized complexity and has trigg…
Using Duality in Circuit Complexity
Silke Czarnetzki, Andreas Krebs
We investigate in a method for proving separation results for abstract classes of languages. A well established method to characterize varieties of regular languages are identities…
Small Depth Proof Systems
Andreas Krebs, Nutan Limaye, Meena Mahajan +1
A proof system for a language L is a function f such that Range(f) is exactly L. In this paper, we look at proofsystems from a circuit complexity point of view and study proof syst…
Streaming algorithms for recognizing nearly well-parenthesized expressions
Andreas Krebs, Nutan Limaye, Srikanth Srinivasan
We study the streaming complexity of the membership problem of 1-turn-Dyck2 and Dyck2 when there are a few errors in the input string. 1-turn-Dyck2 with errors: We prove that there…