NDLI: Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings

Content Provider	IEEE Xplore Digital Library
Author	Dadush, D. Peikert, C. Vempala, S.
Copyright Year	2011
Abstract	We give a novel algorithm for enumerating lattice points in any convex body, and give applications to several classic lattice problems, including the Shortest and Closest Vector Problems (SVP and CVP, respectively) and Integer Programming (IP). Our enumeration technique relies on a classical concept from asymptotic convex geometry known as the M-ellipsoid, and uses as a crucial subroutine the recent algorithm of Micciancio and Voulgaris (STOC 2010)for lattice problems in the l2 norm. As a main technical contribution, which may be of independent interest, we build on the techniques of Klartag (Geometric and Functional Analysis, 2006) to give an expected 2^O(n)-time algorithm for computing an M-ellipsoid for any n-dimensional convex body. As applications, we give deterministic 2^O(n)-time and -space algorithms for solving exact SVP, and exact CVP when the target point is sufficiently close to the lattice, on n-dimensional lattices in any (semi-)norm given an M-ellipsoid of the unit ball. In many norms of interest, including all lp norms, an M-ellipsoid is computable in deterministic poly(n) time, in which case these algorithms are fully deterministic. Here our approach may be seen as a derandomization of the â€œAKS sieveâ€for exact SVP and CVP (Ajtai, Kumar, and Siva Kumar, STOC2001 and CCC 2002). As a further application of our SVP algorithm, we derive an expected O(f(n))^n-time algorithm for Integer Programming, where f(n) denotes the optimal bound in the so-called â€œflatnesstheorem, â€ which satisfies f(n) = O(n^(4/3) polylog(n))and is conjectured to be f(n) = O(n). Our runtime improves upon the previous best of O(n^2)^n by Hildebrand and Koppe(2010).
Starting Page	580
Ending Page	589
File Size	576372
Page Count	10
File Format	PDF
ISBN	9781457718434
ISSN	02725428
e-ISBN	9780769545714
DOI	10.1109/FOCS.2011.31
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-10-22
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Lattices Ellipsoids Algorithm design and analysis Approximation algorithms Approximation methods Vectors M-ellipsoid Shortest/Closest Vector Problem Integer Programming Lattice Point Enumeration
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Enumerative algorithms for the shortest and closest lattice vector problems in any norm via m-ellipsoid coverings (2010).

Enumerative lattice algorithms in any norm via m-ellipsoid coverings (2011)

Enumerative lattice algorithms in any norm via m-ellipsoid coverings (2011)

Enumerative Lattice Algorithms in Any Norm via M-Ellipsoid Coverings

Faster Provable Sieving Algorithms for the Shortest Vector Problem and the Closest Vector Problem on Lattices in $ℓ_{p}$ Norm

Enumerative lattice algorithms in any norm via mellipsoid coverings

A lattice-based threshold secret sharing scheme

Sharing secret using lattice construction

Lattice sparsification and the approximate closest vector problem (2012).

Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings

Similar Documents

Enumerative algorithms for the shortest and closest lattice vector problems in any norm via m-ellipsoid coverings (2010).

Enumerative lattice algorithms in any norm via m-ellipsoid coverings (2011)

Enumerative lattice algorithms in any norm via m-ellipsoid coverings (2011)

Enumerative Lattice Algorithms in Any Norm via M-Ellipsoid Coverings

Faster Provable Sieving Algorithms for the Shortest Vector Problem and the Closest Vector Problem on Lattices in $ℓ_{p}$ Norm

Enumerative lattice algorithms in any norm via mellipsoid coverings

A lattice-based threshold secret sharing scheme

Sharing secret using lattice construction

Lattice sparsification and the approximate closest vector problem (2012).

Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings