English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Schnorr’s algorithm for finding an approximation for the shortest nonzero vector in an n-dimensional lattice depends on a parameter k. He proved that for a fixed k ≤ n his algorithm (block 2k-reduction) provides a lattice vector whose length is greater than the length of a shortest nonzero vector in the lattice by at most a factor of (2k)2n/k. (The time required by the algorithm depends on k.) We show that if k = o(n), this bound on the performance of Schnorr’s algorithm cannot be improved (apart from a constant factor in the exponent). Namely, we prove the existence of a basis in Rn which is KZ-reduced on all k-segments and where the ratio ‖b1‖/shortest(L) is at least kcn/k. Noting that such a basis renders all versions of Schnorr’s algorithm idle (output = input), it follows that the quantity kcn/k is a lower bound on the approximation ratio any version of Schnorr’s algorithm can achieve on the shortest vector problem. This proves that Schnorr’s analysis of ∗A preliminary version of this paper has appeared in the Proc. 35th ACM Symp. on Theory of Computing [2]. ACM Classification: F.2.2, G.2 AMS Classification: 68Q25, 68W40, 68W25, 11H55, 11H99, 52C07, 60D05

Optimal lower bounds for the Korkine-Zolotareff parameters of a lattice and for Schnorr's algorithm for the shortest vector problem