The Complexity of Geometric Problems in High Dimension

DOI10.1007/978-3-642-13562-0_5zbMATH Open1284.68283OpenAlexW1871232634MaRDI QIDQ3569062FDOQ3569062

Christian Knauer

Publication date: 17 June 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-13562-0_5

Recommendations

• On the complexity of some geometric problems in unbounded dimension
• scientific article; zbMATH DE number 4014033
• Complexity of some geometric and topological problems
• A geometric approach to complexity
• Geometric complexity theory: an introduction for geometers
• Geometry and complexity theory
• Geometry and the complexity of matrix multiplication
• On the complexity of some geometric problems with fixed parameters
• Geometric complexity of embeddings in \(\mathbb R^d\)

zbMATH Keywords

lower boundsparameterized complexitygeometric dimensionexponential-time hypothesis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (6)

• Fixed-parameter complexity and approximability of norm maximization
• Title not available (Why is that?)
• Editorial. Approximation and geometry in high dimensions
• A combinatorial branch-and-bound algorithm for box search
• The Knaster problem and the geometry of high-dimensional cubes
• Title not available (Why is that?)

This page was built for publication: The Complexity of Geometric Problems in High Dimension

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