分章节评论

　从头再来一遍。
　　
　　第一章 　
　　1.7节，应该更明确的说一下，每次移动Ri或Li的内容时，需要另外一条带子的帮助，即，先复制到另外一条带子上，再从另外一条带子复制到本带子的另一个区域里。（看的不仔细，同事提出来的，我觉得对。在其他书中，常常强调2带模拟多带是O(n log n)量级的）

现在网上有正版的pdf 啊 我发现了

是写的够乱的，这不是一个整体的书价，更多的是一些证明细节的讨论。
零知识系统大概就很复杂了足以作为一个研究方向。没去专门关注过ZPP和BPP的研究，似乎曾经有一个报告是这种类的分层定理。

第21章 Expanders和extractors

目前只看完了前四章（关于expander的部分）。
写的很好，读下来很舒服。

技术细节方面：
我觉得Rotation map不仅是置换，而且还是两两对换，即G(G(v,i))=(v,i)，所以其对应的矩阵是对称的。这个好像在引理21.18中分析式子21.9时有点用。

第四节的算法复杂度的简析：
存储起始点 s \in [D^k n]
存储目前到达的点 t \in [D^k n]
存储一个代表长O(log n)步路径的串，每步需常数空间，因为只有常数D种走法
存储k=10 log n个数 m_i \in [50], 代表在G_i上走到了第几步了。
t依据p \in [D] 在G_k上走一步，即把G_k R H的 Rotation map 作用在第k层的<u,v,i,b>上50次，m_i记录走到第几次了，其中t=<u,v>, p的第m_i个分量=<i,b> \in [d], 。按定义来，b=0的情况略过，完成时 m_k=m_k+1，其余的m_i变成0。b=1时，要把G_k的 Rotation map作用在第k-1层的<u,v,i,b> (这里的<u,v>是第k层的u，这里的<i,b>是第k层的v的第m_{k-1}个分量)，完成方法一样，完成时 m_k=m_k+1。

小误：公式21.2 中 2D+1应为2D
24.4.1节中的claim中，度好像应为d^50而不是d^20

写的好乱啊,零知识系统是不是本身就不是很难?ZPP好像没有BPP研究的多?

　　第19章 ？？？与纠错码
　　
　　不知怎么翻译好。漏了一些章没写，也不补了。
　　
　　这章有很多地方的细节都省略了，不知道怎么补。最费解的一个是，在Local list decoder 和 Local decoder的定义里面都有正确概率大于2/3，但不知道在相应的定理（定理19.21和19.27，都是反证，假设有一个能在一部分输入x上正确计算f的circuit，要构造一个完全正确计算f的circuit）中，怎么构造出一个circuit（无概率的）。

第17章 计数复杂性

我这个版本的证明perm是#P完全的的定理中，clause gadget的图出问题了，外圈的三个点中，应该只有一对之间有边；另外，对XOR gadget的分析实在是少。

Toda定理的证明没有细看，感觉不如以前看原始文章的证明舒服。

　　第15章 证明复杂性
　　
　　引理15.2的证明要找一个 n/3 < comp(C) < 2n/3 的C。稍微补充一点，起始的大约m^3个clause，其comp很小，要么是0，要么是1。在这个resolution最后，一定会找到P_{ij} 和 \not P_{ij}，他们俩中一定有一个的comp很大，超过n/2（其实是P_{ij}很大，n）。
　　
定理的证明是对n-t调用此引理。不知道怎么说明每次把一个P_ij
赋值成真之后，就会从原对PHP^{n}_{n-1}的resolution refutation得到一个对PHP^{n-1}_{n-2}的resolution refutation。但是，只需验证仍能找到一个 n/3 < comp(C) < 2n/3 的C就好了，这个好像是对的。

　　说n^2/10 小于 2（n-t）^2/9 不准确 （在条件 t<n/3 下）。但仔细算算 log _2 (10/9)，把t<n/3 算得更强更准确点，会发现刚好对。
　　
　　定理15.4
　　只说了思想，没好好证明，没提到circuit是什么样的。我试着弄出那个circuit，一点也看不出来要S^2那么大。resolution里每个clause对应一个gate。每次计算，如果是消的x，或者y，得到新clause，只依赖于前两个clause对应的gate的值；如果是消z的，还依赖z的值（是一个三元函数）。感觉是\bigO (S) 量级的。说清细节要打太多字，我也没十分想清楚。

第14章
　　
　　单调线路下界，没想清楚在用sunflower引理的时候，如果Z是空集，应该添加什么。（一般情况下，添加 $C_Z$）
　　
　　最近忙，没时间写。

第十二章 Decision Tree

难道老了，定理12.5费了我半天劲。也许聪明人一下子就能看懂，还是解释一下这个证明吧。

第一步，找一个 x_0，f(x_0)=0，假设它的certificate set S={s_1,s_2, \ldots, s_C} （可能没这么大），decision tree的前C层是个完全二叉树，第i层的节点里是s_i。

走完前C层后 {0,1}^n里的所有x，依据x|_S的值，分成了2^C个子集。

任取一个x，f(x)=1，x的certificate set记做S'，S'与S的交非空。假设x落入2^C个子集中的某一个，记做A。

第二步，就考虑A所在的decision tree的节点怎么走下去。

和第一步类似，从A中取一个x_1，f(x_1)=0,它的certifecate set记做S''。……

同理可证明S'-S和S''-S的交集非空。

如此下去。最终S'被挖成空集了，x最终落入一个集合，此集合里所有元素在S'上的值相同。

因为放假，下一次更新可能会很久以后。

第十章 量子计算

写的比较高屋建瓴，不注重细节；抠细节的话，读起来很费劲。

傅里叶变换（10.6.1节），在基向量上应该实现的变换这样看比较好理解，|x_1\ldots x_m> ----> \sum_y w^{(x_1\ldotsx_n) \cdot (y_n \ldots y_1)} |y_1 \ldots y_m>。 在快速傅里叶变换的递归中，w的指数是xy，每次递归是去掉了x的最高位和y的末位，所以把y倒过来比较好，这样每次去掉了x_1 和y_1，x_1经过一个Hardmard变换后也就变成了y_1。

第一遍没仔细读算法框里的描述，刚才看了一下发现，算法过程里的确有个交换两个比特的过程。

我也看的是那个电子版 什么时候出书买一本