Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9657696 | Theoretical Computer Science | 2005 | 9 Pages |
Abstract
Our approach also yields connections between the complexity of some (polynomial time) high-dimensional search problems and some NP-hard problems. For example, if there are sufficiently faster algorithms for computing the diameter of n points in â1, then there is an (2-ε)n algorithm for MAX-LIN. These results may be construed as either lower bounds on the high-dimensional problems, or hope that better algorithms exist for the corresponding hard problems.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ryan Williams,