Lower bounds for approximate LDCs

Abstract: We study an approximate version of

q

-query LDCs (Locally Decodable Codes) over the real numbers and prove lower bounds on the encoding length of such codes. A

q

-query

(a l p h a, d e l t a)

-approximate LDC is a set

V

of

n

points in

m a t h b b R^{d}

so that, for each

i i n [d]

there are

O m e g a (d e l t a n)

disjoint

q

-tuples

(v e c u_{1}, l d o t s, v e c u_{q})

in

V

so that

e x t s p a n (v e c u_{1}, l d o t s, v e c u_{q})

contains a unit vector whose

i

'th coordinate is at least

a l p h a

. We prove exponential lower bounds of the form

n g e q 2^{O m e g a (a l p h a d e l t a s q r t d)}

for the case

q = 2

and, in some cases, stronger bounds (exponential in

d

).

Recommendations

Cited in

(4)

This page was built for publication: Lower bounds for approximate LDCs