scientific article; zbMATH DE number 6381680

MaRDI QIDQ2934634zbMATH OpenFDO

Authors Jeff Edmonds

Publication date 18 December 2014

Mathematics Subject Classification ID

Metric spaces, metrizability (54E35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10) Randomized algorithms (68W20)

Recommendations

• Embedding into \(l_{\infty }^{2}\) is easy, embedding into \(l_{\infty}^{3}\) is NP-complete
• Embeddability in \(\mathbb R^3\) is NP-hard
• Embeddability in R^3 is NP-hard
• Isomorphic embedding of \(\ell_p^n\), \(1<p<2\), into \(\ell_1^{(1+\varepsilon)n}\)
• scientific article; zbMATH DE number 7051255
• Hardness of embedding simplicial complexes in R^d
• Hardness of almost embedding simplicial complexes in \(\mathbb {R}^d\)
• The embedding \(O(2m,2^ k)\leq Sp(2m,2^ k)\)
• Embedding l ^{p , ∞} into L ^{p , ∞} [0, 1] Complementably
• Automata, Languages and Programming

Cited in

(3)

• Algorithms for \(\ell_{1}\)-embeddability and related problems
• scientific article; zbMATH DE number 2079382 (Why is no real title available?)
• Embedding into \(l_{\infty }^{2}\) is easy, embedding into \(l_{\infty}^{3}\) is NP-complete

This page was built for publication:

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