Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > CSP REFUTATION:
Reports tagged with CSP refutation:
TR22-101 | 15th July 2022
Omar Alrabiah, Venkatesan Guruswami, Pravesh Kothari, Peter Manohar

A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation

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 >>>




ISSN 1433-8092 | Imprint