A double exponential lower bound for the distinct vectors problem

DOI10.23638/DMTCS-22-4-7MaRDI QIDQ3386631zbMATH OpenFDO

Authors Marcin Pilipczuk, Manuel Sorge

Publication date 5 January 2021

Full work available at URL https://arxiv.org/abs/2002.01293, https://dmtcs.episciences.org/6789

zbMATH Keywords

computational complexitydata miningfeature selectionparameterized algorithms

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Learning and adaptive systems in artificial intelligence (68T05)

Recommendations

• Exploiting hidden structure in selecting dimensions that distinguish vectors
• scientific article; zbMATH DE number 6783431
• Slightly superexponential parameterized problems
• More consequences of falsifying SETH and the orthogonal vectors conjecture
• On problems as hard as CNF-SAT

Cites work

• scientific article; zbMATH DE number 53312 (Why is no real title available?)
• On the complexity of k-SAT
• The parameterized complexity of dependency detection in relational databases
• Which problems have strongly exponential complexity?

Cited in

(4)

• Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover
• Tight (double) exponential bounds for identification problems: locating-dominating set and test cover
• Tight (double) exponential bounds for identification problems: locating-dominating set and test cover
• Exploiting hidden structure in selecting dimensions that distinguish vectors

This page was built for publication: A double exponential lower bound for the distinct vectors problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3386631)