research
∙
06/02/2022
On the Parallel Parameterized Complexity of MaxSAT Variants
In the maximum satisfiability problem (MAX-SAT) we are given a propositi...
share
research
∙
01/21/2022
On the Satisfaction Probability of k-CNF Formulas
The satisfaction probability σ(ϕ) := _β:vars(ϕ) →{0,1}[βϕ] of a proposit...
research
∙
01/21/2021
Work-sensitive Dynamic Complexity of Formal Languages
Which amount of parallel resources is needed for updating a query result...
research
∙
02/20/2019
Towards Work-Efficient Parallel Parameterized Algorithms
Parallel parameterized complexity theory studies how fixed-parameter tra...
research
∙
01/10/2019
On the Descriptive Complexity of Color Coding
Color coding is an algorithmic technique used in parameterized complexit...
research
∙
07/10/2018
Computing Kernels in Parallel: Lower and Upper Bounds
Parallel fixed-parameter tractability studies how parameterized problems...
research
∙
01/02/2018