【Under Construction】Yoder, Low, Chuang. Fixed-point quantum search with an optimal number of queries
Abstract.
H. Ramech, V.Vinay. String matching in $\tilde{O}(\sqrt n + \sqrt m)$ quantum time (2003)
Abstract. 本文是 https://doi.org/10.1016/S1570-8667(03)00010-8 的阅读笔记。他们尝试把 https://doi.org/10.1137/0220002 的技术用在了量子计算机上，发现很有道理。很遗憾的是作者好像不是量子计算从业者，他们的很多 approach 都是有问题的，但也不是不能修复。因为他的思路非常 trivial，所以我们有精力帮他们重新算一遍。最后一节“处理周期性串”看起来比较对，但我们放弃仔细验证了。
Uzi Vishkin. Deterministic Sampling–A New Technique for Fast Pattern Matching (1991)
Abstract. 本文是 https://doi.org/10.1137/0220002 的阅读笔记。文中提出了一种确定性的采样方法用于加速字符串匹配，由此得到了操作次数 $O(n)$ 时间 $O(\log^* n)$ 的并行算法。
文中用到了大量的分治、分块、复杂度平衡、递归的技巧，虽然这些无非是思考并行算法的时候的重点考虑方向，但第一次见的时候感觉还是比较奇妙，整个论文读完像做了一道超大的构造题。
Revision | 抽象代数小常识
Abstract. 本文实际上是离散数学与结构上半学期的笔记整理。本课实际上包含了其他内容，比如朴素集合论中的势理论，命题逻辑，一阶逻辑及（不）完备定理，在合集 category: Discrete Math 中有所收录，不再重复。本文只写抽象代数的内容。
本文最后一节有许多定理的证明有待补充，包括后两条 Sylow 定理的证明，分裂域相关理论，和最后因子分解算法中关于 $\pm 1$ 出现概率均等的断言。
【Under Construction】一些逻辑话题：递归论初步与哥德尔不完备定理
Abstract. 离散数学与结构作业出了一个题考察对哥德尔不完备定理的深度理解，但是他上课实在是讲得过于粗糙，于是我们被迫完整阅读一遍相关理论。参考资料是 Dirk van Dalen, Logic and Structure(Fifth Edition), Springer(2013) Chapter 8 Godel’s Theorem。
常微分方程（1.5）应用举例
Abstract. 本文讨论几个拥有前置知识初等积分法之后可以解决的问题。解决问题的过程中用到了一些建模技巧和神秘手法，具有一些学习价值。此外后面几个关于生态的模型导出的结果是富有趣味和现实意义的，可供消遣。
一些逻辑话题：如何证明自然演绎系统的一致性、完备性，以及直觉主义逻辑
Abstract. 本文讨论了几个形式系统的语法和语义之间联系的问题，包括证明自然演绎系统的一致性和完备性，以及直觉主义逻辑中不能推导出 $(\neg\neg P)\rightarrow P$。阅读本文需要的对数理逻辑的理解大概与清华大学出版社的“数理逻辑与集合论”前三章一致，如果没有相关知识可以参考这篇笔记。但本文不采用其中定义的公理系统和证明方式，这点在“声明与记号”中有所说明。