Explicit SoS lower bounds from high-dimensional expanders.
Irit DinurYuval FilmusPrahladh HarshaMadhur TulsianiPublished in: CoRR (2020)
Keyphrases
- lower bound
- high dimensional
- upper bound
- optimal solution
- dimensionality reduction
- low dimensional
- branch and bound
- objective function
- parameter space
- np hard
- sparse data
- nearest neighbor
- branch and bound algorithm
- high dimensional problems
- lower and upper bounds
- noisy data
- similarity search
- worst case
- multi dimensional
- manifold learning
- input space
- upper and lower bounds
- gene expression data
- high dimensionality
- high dimensional data
- variable selection
- quadratic assignment problem
- image registration
- data points