Lower Bounds for Approximate LDC

Jop Briët, Zeev Dvir, Guangda Hu +1

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 $(\alpha ,\delta )$-a…