The remote set problem on lattices
From MaRDI portal
Publication:2353188
DOI10.1007/s00037-014-0094-zzbMath1332.68077OpenAlexW2024202161MaRDI QIDQ2353188
Publication date: 8 July 2015
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-014-0094-z
Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Lattices and convex bodies (number-theoretic aspects) (11H06) Lattice packing and covering (number-theoretic aspects) (11H31) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of the covering radius problem
- Limits on the hardness of lattice problems in \(\ell_{p}\) norms
- A note on the distribution of the distance from a lattice
- On Lovász' lattice reduction and the nearest lattice point problem
- Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
- A hierarchy of polynomial time lattice basis reduction algorithms
- Does co-NP have short interactive proofs ?
- Factoring polynomials with rational coefficients
- On the limits of nonapproximability of lattice problems
- Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard
- A probabilistic approach to the geometry of the \(\ell^n_p\)-ball
- Approximating CVP to within almost-polynomial factors is NP-hard
- A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations
- Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors
- Lattice problems and norm embeddings
- Lattice problems in NP ∩ coNP
- Hardness of approximating the shortest vector problem in lattices
- Lattice-based Cryptography
- Deterministic Approximation Algorithms for the Nearest Codeword Problem
- Six Standard Deviations Suffice
- Minkowski's Convex Body Theorem and Integer Programming
- Balancing vectors and convex bodies
- Almost Perfect Lattices, the Covering Radius Problem, and Applications to Ajtai's Connection Factor
- A sieve algorithm for the shortest lattice vector problem
- On the Lattice Isomorphism Problem
- Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
This page was built for publication: The remote set problem on lattices
