Abstract
I will present an exponential lower bound for the codeword length of 2-query relaxed locally decodable codes (RLDCs). Combined with the almost linear constructions shown by Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (SICOMP 2006) for some large but constant number of queries, this implies a sharp transition in the codeword length from super-exponential to polynomial, for some constant query complexity. In search for this threshold, I will further mention recent results for 3-query RLDCs and beyond.
Based on joint works with Alex Block, Jeremiah Blocki, Kuan Cheng, Xin Li, Yu Zheng, and Minshen Zhu, and with Vinayak Kumar, Peter Manohar, and Geoffrey Mon.