johnson算法
我们首先介绍“ON THE SIZE OF KAKEYA SETS IN FINITE FIELDS”这篇文章，之前在计算理论概论上就听闻过这篇文章，这次在研究多项式与PRG中又碰巧遇到。首先介绍一下一般的kakeya set背景：我们希望在R^n中找到一个集合，其中包含任意方向的长度为1的线段，有著名的kakeya猜想，即所有kakeya set的hausdorff dimension均为n，直观的来说，可以从下面的wikipedia的通俗解释中大致了解hausdorff dimension：
该猜想与一系列调和分析、数论与PDE问题相关，目前仅对n=2的情形证明了猜想。
1999年，Wolff首先提出能否在有限域上证明一个相似的结论，即在F^n上是否有kakeya set的大小至少为q^n量级才能包含每一条线：
Wolff在1999年的文章中证明了Ω(q^{(n + 2)/2})的结论，随后被陶哲轩等人用加性集合的数论性质改进到了Ω(q^{4n/7})。
本文作者Zeev Dvir作为一个CS在读博士生，敏锐地意识到有限域上的情形可以转换为多项式有多少零点就一定为零多项式的情况，于是引入了在kakeya set上取值为0的n元d次多项式，试图说明一旦kakeya set大小过小，就存在这样一个非平凡n元d次多项式在kakeya set上取值为0，再由于kakeya set包含每个方向的直线，进而推出在所有点上取值为0，由Schwartz-Zippel随机算法的分析，我们容易证明一个非平凡n元d次多项式在F^n中任取一个点，取值非0的概率至少为d/q，从而推出矛盾。具体方法如下：
从而得到了q^{n – 1}量级，注意到这里没有能到q^n量级的主要原因是只考虑了n元d次齐次多项式的次数，陶哲轩和Noga Alon都发现齐次要求是可以去掉的，因为在上述证明过程中齐次只是为了保证乘以一个常数的不变形，而通过更细致的多项式分析可以避免这一问题：
然后我们简单介绍一下Johnson Bound，直观而言，就是讨论一组比较稀疏的向量如果hamming distance足够远，那么就比较少。这一想法之后被运用于证明list decoding的解虽然不唯一，但个数一定不多，可以控制在多项式级别。本文作者采用Pseudorandomness By Salil P. Vadhan中的视角进行介绍，并进一步简介reed-solomon码list decoding的方法。定义可以详见pseudorandomness系列中对于第五章的定义。
首先我们介绍一个引理：对于R^n，至多选出n+1个向量，使得两两内积小于0，证明采用数学归纳法和反证法，对于n+1维情形，选定一个向量，将其余向量投影到其法平面即可化归到n维情形，归纳基础显然。
然后我们证明Johnson Bound：对于含有1的个数w不超过n – sqrt(n(n-d)) < d的一组两两hamming distance不小于d的n维向量，其中向量个数不超过n(q – 1) + 1
证明方法便是将n维向量的每一个维的元素映射到R^q中的一个超平面上的点(-1 + c,-1 + c,…,-1 + c,q-1 + c,-1 + c,…,-1 + c)（注意到对应的q个点显然在一个超平面上，从而是q-1维的），然后说明选取合适的c，在已知条件下能保证两两内积小于0，利用引理即得证。
事实上，类似的利用欧氏空间内积性质的下界证明法还是非常常见的，例如之前某篇推送中介绍到的关于pairwise independent family的size lower bound用到了类似的但是直接构造正交向量的方法：
接下来我们便可以考察Reed-Solomon码如何list-decoding，注意到1-sqrt(d/q)对应着Johnson Bound所放出的上界
注意到对于一元多项式分解的随机算法，我们在数论基础（4）中已做介绍，从而以高概率，我们能在多项式时间求出所需要的list。
