3-query locally correctable codes are codes where any particular location of a corrupted word can be corrected with high probability by looking at just three other locations. A sequence of recent works has tried to find the correct relationship between a 3-query LCC's block length and its dimension. We will look at the proof of Alrabiah and Guruswami's near-optimal result. Though it needs the code to be binary and linear, it is a nice short proof that proceeds via rainbow cycles in graphs.

Paper link: https://arxiv.org/abs/2404.05864