49 citations
- Saarland UniversityDE9 papers
- Max Planck Institute for InformaticsDE5 papers
- Max Planck Institute for Software SystemsDE2 papers
- Max Planck SocietyDE2 papers
- Monash UniversityAU2 papers
- University of StuttgartDE2 papers
- Aarno LabsUS1 paper
- Braude College of Engineering KarmielIL1 paper
- California University of PennsylvaniaUS1 paper
- Deutsches Zentrum für Luft- und Raumfahrt e. V. (DLR)DE1 paper
- Duke UniversityUS1 paper
- Fraunhofer Institute for Communication, Information Processing and ErgonomicsDE1 paper
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2022★ 1 cited
Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction
Dániel Marx
Conditional lower bounds based on , the Exponential-Time Hypothesis (ETH), or similar complexity assumptions can provide very useful information about what type of algori…
cs.CC2021★ 5 cited
Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth
Dániel Marx, Govind S. Sankar, Philipp Schepper
For the General Factor problem we are given an undirected graph and for each vertex a finite set of non-negative integers. The task is to decide if there is a…
cs.CC2020★ 1 cited
Fine-Grained Complexity of Regular Expression Pattern Matching and Membership
Philipp Schepper
The currently fastest algorithm for regular expression pattern matching and membership improves the classical O(nm) time algorithm by a factor of about log^{3/2}n. Instead of focus…