Paper Info
Title
Improvements on Reductions among Different Variants of SVP and CVP
Abstract
It is well known that Search SVP is equivalent to Optimization SVP. However, the classical reduction from Search SVP to Optimization SVP by Kannan needs polynomial times of calls to the oracle that solves Optimization SVP. In this paper, a new rank-preserving reduction is presented with only one call to the Optimization SVP oracle. The idea also leads to a similar direct reduction from Search CVP to Optimization CVP with only one call to the corresponding oracle. Both of the reductions above can be generalized for <InlineEquation ID=\"IEq1\" <EquationSource Format=\"TEX\"$$l_p$$</EquationSource> <EquationSource Format=\"MATHML\" <math xmlns:xlink=\"http://www.w3.org/1999/xlink\" <msub> <mi>l</mi> <mi>p</mi> </msub> </math> </EquationSource> </InlineEquation> norm with <InlineEquation ID=\"IEq2\" <EquationSource Format=\"TEX\"$$p\\in \\mathbb {Z}^{+} $$</EquationSource> <EquationSource Format=\"MATHML\" <math xmlns:xlink=\"http://www.w3.org/1999/xlink\" <mrow> <mi>p</mi> <mo>∈</mo> <msup> <mrow> <mi mathvariant=\"double-struck\"Z</mi> </mrow> <mo>+</mo> </msup> </mrow> </math> </EquationSource> </InlineEquation>. On the other hand, whether the search and optimization variants of approximate SVP are computationally equivalent is an outstanding open problem. Recently, Cheng gave a reduction from Search <InlineEquation ID=\"IEq3\" <EquationSource Format=\"TEX\"$$\\text {SVP}_\\gamma $$</EquationSource> <EquationSource Format=\"MATHML\" <math xmlns:xlink=\"http://www.w3.org/1999/xlink\" <msub> <mtext>SVP</mtext> <mi mathvariant=\"italic\"γ</mi> </msub> </math> </EquationSource> </InlineEquation> to Optimization <InlineEquation ID=\"IEq4\" <EquationSource Format=\"TEX\"$$\\text {SVP}_{\\gamma ^{'}}$$</EquationSource> <EquationSource Format=\"MATHML\" <math xmlns:xlink=\"http://www.w3.org/1999/xlink\" <msub> <mtext>SVP</mtext> <msup> <mi mathvariant=\"italic\"γ</mi> <msup> <mrow/ <mo>'</mo> </msup> </msup> </msub> </math> </EquationSource> </InlineEquation>, where <InlineEquation ID=\"IEq5\" <EquationSource Format=\"TEX\"$$\\gamma ^{'}=\\gamma ^{\\frac{1}{n(n-1)\\log _{2}\\gamma n}}$$</EquationSource> <EquationSource Format=\"MATHML\" <math xmlns:xlink=\"http://www.w3.org/1999/xlink\" <mrow> <msup> <mi mathvariant=\"italic\"γ</mi> <msup> <mrow/ <mo>'</mo> </msup> </msup> <mo>=</mo> <msup> <mi mathvariant=\"italic\"γ</mi> <mfrac> <mn>1</mn> <mrow> <mi>n</mi> <mrow> <mo stretchy=\"false\"(</mo> <mi>n</mi> <mo>-</mo> <mn>1</mn> <mo stretchy=\"false\")</mo> </mrow> <msub> <mo>log</mo> <mn>2</mn> </msub> <mi mathvariant=\"italic\"γ</mi> <mi>n</mi> </mrow> </mfrac> </msup> </mrow> </math> </EquationSource> </InlineEquation> is much smaller than <InlineEquation ID=\"IEq6\" <EquationSource Format=\"TEX\"$$\\gamma $$</EquationSource> <EquationSource Format=\"MATHML\" <math xmlns:xlink=\"http://www.w3.org/1999/xlink\" <mi mathvariant=\"italic\"γ</mi> </math> </EquationSource> </InlineEquation>. We slightly improve the reduction by making <InlineEquation ID=\"IEq7\" <EquationSource Format=\"TEX\"$$\\gamma ^{'}=\\gamma ^{\\frac{O(\\log _{2}n)}{n(n-1)\\log _{2}\\gamma n}}$$</EquationSource> <EquationSource Format=\"MATHML\" <math xmlns:xlink=\"http://www.w3.org/1999/xlink\" <mrow> <msup> <mi mathvariant=\"italic\"γ</mi> <msup> <mrow/ <mo>'</mo> </msup> </msup> <mo>=</mo> <msup> <mi mathvariant=\"italic\"γ</mi> <mfrac> <mrow> <mi>O</mi> <mo stretchy=\"false\"(</mo> <msub> <mo>log</mo> <mn>2</mn> </msub> <mi>n</mi> <mo stretchy=\"false\")</mo> </mrow> <mrow> <mi>n</mi> <mrow> <mo stretchy=\"false\"(</mo> <mi>n</mi> <mo>-</mo> <mn>1</mn> <mo stretchy=\"false\")</mo> </mrow> <msub> <mo>log</mo> <mn>2</mn> </msub> <mi mathvariant=\"italic\"γ</mi> <mi>n</mi> </mrow> </mfrac> </msup> </mrow> </math> </EquationSource> </InlineEquation>. In addition, a reduction from Search <InlineEquation ID=\"IEq8\" <EquationSource Format=\"TEX\"$$\\text {CVP}_\\gamma $$</EquationSource> <EquationSource Format=\"MATHML\" <math xmlns:xlink=\"http://www.w3.org/1999/xlink\" <msub> <mtext>CVP</mtext> <mi mathvariant=\"italic\"γ</mi> </msub> </math> </EquationSource> </InlineEquation> to Optimization <InlineEquation ID=\"IEq9\" <EquationSource Format=\"TEX\"$$\\text {CVP}_{\\gamma ^{'}}$$</EquationSource> <EquationSource Format=\"MATHML\" <math xmlns:xlink=\"http://www.w3.org/1999/xlink\" <msub> <mtext>CVP</mtext> <msup> <mi mathvariant=\"italic\"γ</mi> <msup> <mrow/ <mo>'</mo> </msup> </msup> </msub> </math> </EquationSource> </InlineEquation> with <InlineEquation ID=\"IEq10\" <EquationSource Format=\"TEX\"$$\\gamma ^{'}=\\gamma ^{\\frac{1}{n\\lceil n/2 + \\log _{2}\\gamma \\cdot \\text {dist}(t,\\mathcal {L}(B))\\rceil }}$$</EquationSource> <EquationSource Format=\"MATHML\" <math xmlns:xlink=\"http://www.w3.org/1999/xlink\" <mrow> <msup> <mi mathvariant=\"italic\"γ</mi> <msup> <mrow/ <mo>'</mo> </msup> </msup> <mo>=</mo> <msup> <mi mathvariant=\"italic\"γ</mi> <mfrac> <mn>1</mn> <mrow> <mi>n</mi> <mo>﾿</mo> <mi>n</mi> <mo stretchy=\"false\"/</mo> <mn>2</mn> <mo>+</mo> <msub> <mo>log</mo> <mn>2</mn> </msub> <mi mathvariant=\"italic\"γ</mi> <mo>·</mo> <mtext>dist</mtext> <mrow> <mo stretchy=\"false\"(</mo> <mi>t</mi> <mo>,</mo> <mi mathvariant=\"script\"L</mi> <mrow> <mo stretchy=\"false\"(</mo> <mi>B</mi> <mo stretchy=\"false\")</mo> </mrow> <mo stretchy=\"false\")</mo> </mrow> <mo>﾿</mo> </mrow> </mfrac> </msup> </mrow> </math> </EquationSource> </InlineEquation> is also presented.
Year
DOI
Venue
2013
10.1007/978-3-319-05149-9_3
WISA
Keywords
Field
DocType
reduction,lattice
Combinatorics,Open problem,Lattice (order),Polynomial,Computer science,Algorithm,Theoretical computer science,Norm (mathematics)
Conference
Volume
ISSN
Citations 
8267
0302-9743
1
PageRank 
References 
Authors
0.36
14
2
Name
Order
Citations
PageRank
Gengran Hu1203.11
Yanbin Pan23513.29