A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor

DOI10.1016/S0166-218X(02)00216-0zbMath1116.11050OpenAlexW1971488652MaRDI QIDQ1861566

Jin-Yi Cai

Publication date: 9 March 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(02)00216-0

zbMATH Keywords

geometry of numberstransference theoremLattice problemsworst-case/average-case connection

Mathematics Subject Classification ID

Lattice packing and covering (number-theoretic aspects) (11H31) Mean value and transfer theorems (11H60)

Related Items (5)

Discrete Gaussian measures and new bounds of the smoothing parameter for lattices ⋮ New transference theorems on lattices possessing \(n^\varepsilon\)-unique shortest vectors ⋮ On a certain class of positive definite functions and measures on locally compact abelian groups and inner-product spaces ⋮ Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms ⋮ Measure inequalities and the transference theorem in the geometry of numbers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
• On Lovász' lattice reduction and the nearest lattice point problem
• Dual vectors and lower bounds for the nearest lattice point problem
• Factoring polynomials with rational coefficients
• Geometric algorithms and combinatorial optimization
• A relation of primal--dual lattices and the complexity of shortest lattice vector problem
• New bounds in some transference theorems in the geometry of numbers
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• Inequalities for convex bodies and polar reciprocal lattices in \(\mathbb{R}^ n\). II: Application of \(K\)-convexity
• Approximating CVP to within almost-polynomial factors is NP-hard
• Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions
• The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant
• Integer Programming with a Fixed Number of Variables
• Collision-Free Hashing from Lattice Problems
• An Introduction to the Geometry of Numbers
• Disproof of the Mertens conjecture.
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• The complexity of promise problems with applications to public-key cryptography

This page was built for publication: A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor