Closest vector problem .28CVP.29 Lattice problem

-



1 closest vector problem (cvp)

1.1 relationship svp
1.2 hardness results
1.3 sphere decoding





closest vector problem (cvp)

this illustration of closest vector problem (basis vectors in blue, external vector in green, closest vector in red).


in cvp, basis of vector space v , metric m (often l) given lattice l, vector v in v not in l. desired find vector in l closest v (as measured m). in



γ


{\displaystyle \gamma }

-approximation version





cvp


γ




{\displaystyle {\text{cvp}}_{\gamma }}

, 1 must find lattice vector @ distance @



γ


{\displaystyle \gamma }

.


relationship svp

the closest vector problem generalization of shortest vector problem. easy show given oracle





cvp


γ




{\displaystyle {\text{cvp}}_{\gamma }}

(defined below), 1 can solve





svp


γ




{\displaystyle {\text{svp}}_{\gamma }}

making queries oracle. naive method find shortest vector calling





cvp


γ




{\displaystyle {\text{cvp}}_{\gamma }}

oracle find closest vector 0 not work because 0 lattice vector , algorithm potentially output 0.


the reduction





svp


γ




{\displaystyle {\text{svp}}_{\gamma }}







cvp


γ




{\displaystyle {\text{cvp}}_{\gamma }}

follows: suppose input





svp


γ




{\displaystyle {\text{svp}}_{\gamma }}

problem basis lattice



b
=
[

b

1


,

b

2


,
…
,

b

n


]


{\displaystyle b=[b_{1},b_{2},\ldots ,b_{n}]}

. consider basis




b

i


=
[

b

1


,
…
,
2

b

i


,
…
,

b

n


]


{\displaystyle b^{i}=[b_{1},\ldots ,2b_{i},\ldots ,b_{n}]}

, let




x

i




{\displaystyle x_{i}}

vector returned





cvp


γ


(

b

i


,

b

i


)


{\displaystyle {\text{cvp}}_{\gamma }(b^{i},b_{i})}

. claim shortest vector in set



{

x

i


−

b

i


}


{\displaystyle \{x_{i}-b_{i}\}}

shortest vector in given lattice.


hardness results

goldreich et al. showed hardness of svp implies same hardness cvp. using pcp tools, arora et al. showed cvp hard approximate within factor




2


log

1
−
ϵ


⁡
(
n
)




{\displaystyle 2^{\log ^{1-\epsilon }(n)}}

unless



np
⊆
dtime
⁡
(

2

p
o
l
y
(
log
⁡
n
)


)


{\displaystyle \operatorname {np} \subseteq \operatorname {dtime} (2^{poly(\log n)})}

. dinur et al. strengthened giving np-hardness result



ϵ
=
(
log
⁡
log
⁡
n

)

c




{\displaystyle \epsilon =(\log \log n)^{c}}





c
<
1

/

2


{\displaystyle c<1/2}

.


sphere decoding

algorithms cvp, fincke , pohst variant, have been used data detection in multiple-input multiple-output (mimo) wireless communication systems (for coded , uncoded signals). in context called sphere decoding due radius used internal many cvp solutions.


it has been applied in field of integer ambiguity resolution of carrier-phase gnss (gps). called lambda method in field.








Comments

Post a Comment

Popular posts from this blog

Gigantomastia Breast hypertrophy

-
the first recorded case of gigantomastia, diagnosed in 23- or 24-year-old woman, circa 1670. in 1670, physician durston drew illustration of first recorded case of non-gravid gigantomastia; woman died of condition. a painting lam qua of lu-shi, age 42, on april 17, 1848, prior breast reduction surgery. one , extreme case study of gigantomastia dates 1670. patient died 4 months after onset of enlargement. 1 breast removed after woman s death weighed 29 kg (64 lb). on april 17, 1848, 42-year-old woman named lu-shi treated hypertrophy in chinese hospital. treated missionary physician. on december 24, 1849, left breast, measuring 67 cm (26.5 in) in circumference, , weighing 2.7 kg (6 lb), removed in procedure lasting 3 , half minutes. right breast removed 1 month later. measured 61 cm (24 in) in circumference , weighed 2.5 kg (5.5 lb). in 2005, woman reported breasts grew @ puberty nothing c cup in 1 month. when became pregnant first time, b...
Read more

History Conagra Brands

-
the previous conagra brands logo, used until june 2009. in 1971, nebraska consolidated mills changed name conagra , portmanteau of con consolidated , agra, short in english agriculture. 1970s brought company brink of ruin lost money expanding fertilizer, catfish, , pet product industries , commodity speculation wiped out conagra s margins on raw foods. in 1974, c. michael mike harper, experienced food industry executive, took on firm , brought brink of bankruptcy. nonetheless, conagra s business model left vulnerable volatile commodity prices. in response, company set off on two-decade-long buying spree, purchasing on 1 hundred prepared food brands, starting 1980 purchase of banquet foods. moved heavily frozen food business , packaged meat industry, , picked selection of other brands firms rjr nabisco , beatrice foods among others, leveraged buyouts of 1980s resulted in divestiture or breakup of many major american consumer product firms. in 1993 alone purchased $500 million in smal...
Read more

Demographics Union County, Tennessee

-
age pyramid union county at 2000 census, there 17,808 people, 6,742 households , 5,191 families residing in county. population density 80 per square mile (31/km²). there 7,916 housing units @ average density of 35 per square mile (14/km²). racial makeup of county 98.46% white, 0.10% black or african american, 0.23% native american, 0.16% asian, 0.02% pacific islander, 0.17% other races, , 0.86% 2 or more races. 0.79% of population hispanic or latino of race. there 6,742 households of 35.40% had children under age of 18 living them, 62.20% married couples living together, 10.50% had female householder no husband present, , 23.00% non-families. 19.80% of households made of individuals , 7.40% had living alone 65 years of age or older. average household size 2.62 , average family size 2.99. 25.70% of population under age of 18, 8.90% 18 24, 31.00% 25 44, 23.60% 45 64, , 10.80% 65 years of age or older. median age 36 years. every 100 females there 98.80 males. every 100 females age 18 ...
Read more