A code C \colon \{0,1\}^k \to \{0,1\}^n is a q-locally decodable code (q-LDC) if one can recover any chosen bit b_i of the message b \in \{0,1\}^k with good confidence by randomly querying the encoding x = C(b) on at most q coordinates. Existing constructions of 2-LDCs achieve $n = ... more >>>

In this work we observe a tight connection between three topics: NC^0 cryptography, NC^0 range avoidance, and static data structure lower bounds. Using this connection, we leverage techniques from the cryptanalysis of NC^0 PRGs to prove state-of-the-art results in the latter two subjects. Our main result is a quadratic improvement ... more >>>