For every constant odd number of queries q, any q-query locally decodable code has length at least (k/(log k))^(q/(q-2)) up to constants.
Strongly refuting random CSPs below the spectral threshold
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
fields
cs.CC 1years
2024 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
A $k^{\frac{q}{q-2}}$ Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs
For every constant odd number of queries q, any q-query locally decodable code has length at least (k/(log k))^(q/(q-2)) up to constants.