3-Query RLDCs are Strictly Stronger than 3-Query LDCs

Tom Gur, Dor Minzer, Guy Weissenberg +1

We construct $3$-query relaxed locally decodable codes (RLDCs) with constant alphabet size and length $\tilde{O}(k^2)$ for $k$-bit messages. Combined with the lower bound of $\tild…