大概就随便记一记读过的有亮点的东西，觉得很牛逼的东西就分享一下，随缘更新。
当然也不是教程或者阅读笔记。
TCS 是指 Theoretical Computer Science。
Fine-Grained Complexity and Cryptography
这是 MIT 的 Fine-Grained Complexity 课，可以用它的 lecture note 简单学一学。以及它的大作业的 paper list 作为起点我认为是不错的。
Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. Average-Case Fine-Grained Hardness. In STOC 2017.
以下称为 [avg-fg]
声称是第一篇将 fine-grained complexity 与 cryptography 结合起来的工作。
先推导一个重要的 Lemma 1，就是将传统的 random self-reducibility 改造了一下，原本的归约只要多项式复杂度就好了，现在要求复杂度更精细，因此要用比较牛逼的点值和插值。
然后基于这个做出了几个基本问题的 average-case hardness。
然后针对 OV 问题，给出了只用 $\tilde O(n)$ 的验证方法（灵活运用多点求值和快速插值），这样就给出了一个 MA 协议和 Proof of Work。虽然是老竞赛选手了，但还是被秀得头皮发麻
然后它说用 OV 构造的 instance-solution pair 作为 OWF 会证伪 NSETH，因此 OV 的这个 hardness 不太能用来做 OWF。
Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In TCS 2016.
以下称为 [NSETH]
[avg-fg] 在构建 one-way function 的时候说，如果他设计的 one-way function 存在，就会证伪 NSETH 猜想。这篇就是讲 NSETH 猜想。
简单来说，SETH 是说 k-SAT 需要指数时间，而 NSETH 是说 k-UNSAT 在非确定图灵机上也要指数时间。
然后他说证伪 NSETH 会得到一些 circuit lower bound，所以很难证伪。由于不懂电路就先跳过了。
fine-grained reduction 可以在非确定性图灵机上进行，这样就可以使用 NSETH 这个 hardness 了。NSETH 推导出来最有趣的结果应当是，SETH-hard 不能说明 3-SUM-hard 和 APSP-hard。
Rio LaVigne, Andrea Lincoln, and Virginia VassilevskaWilliams. Public-Key Cryptography in the Fine-Grained Setting. In CRYPTO 2019.
以下称为 [pubkey]
老板：“如果 public key 做出来了，那数字签名之类的全套都有了，你代码实现一下，假装数字签名那些是很难很创新的东西，不就把毕设水出来了吗？反正你校的老师都水平低看不懂。”
这篇想要基于 [avg-fg] 继续深入，搞 public key 和 key exchange，顺便深入研究 one-way function。
开局 27 个 definition 让人为之震撼，这套东西居然要基于这么强的限制，花拳绣腿。
而后面基于 Merkle Puzzle 设计具体协议的那部分，特别是证明，还没读懂。要么是我水平低领悟不了她们的奥妙，要么是她们喝了假酒在那乱写。
然后老板的想法大概也是要 fail 的，像“均匀采样一个 3-SUM 问题无解的例子”这样的东西就很不可实现。
Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. Proofs of Work From Worst-Case Assumptions. In CRYPTO 2018.
以下称为 [PoW]
原班人马对 [avg-fg] 的延续。
前半部分是把 OV 问题换成了 kOV 问题重新推了一遍 Proof of Work，但是复杂度算得很假，包括但不限于多点求值和快速插值的复杂度竟然离谱地达到了 $O(n \log^3 n \log p)$、一些步骤细节写得不清不楚。
后面比较有趣的是搞了一个 Zero Knowledge Proof of Work，美中不足的是它根据 ElGamal 来改的，因此用了 Decisional Diffie-Hellman 假设，违背了 Fine-Grained Cryptography 的初衷（使用 Fine-Grained Complexity 中的 hardness）。
Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, and Ryan Williams. Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexit. In ITCS 2022.
以下称为 [improved-ma]
为 $k$-SUM、#Zero-Weight $k$-Clique、$k$-CNF Unsat 设计了高效的 MA 协议。都是多项式/生成函数加上一些神奇的多项式技巧。怎么感觉一直都是同一班人在给 OI/XCPC/学术带来多项式的血雨腥风
这里会发现，$k$-SUM 和 $k$-CNF 都是做经典问题的补问题。因为 MA 协议还是比较爽的，以 $\exists$ 开头的问题（如问是否有解）直接让 prover 把解扔给 verifier 就行了，所以反过来以 $\forall$ 开头的问题（如问是否无解）才是有挑战性的。
但如果尝试给 MA 套上 zero-knowledge，难度就另说了。。。
Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. Matching Triangles and Basing Hardness on an Extremely Popular Conjecture.
以下称为 [matching-triangles]
这篇文章大概干了两件事：一是把很多问题归约到了 $\Delta$-Matching-Triangle 问题上，第二是给出了 $\Delta$-Matching-Triangle 问题的一个优秀的做法。做法是，枚举三种颜色的 size，然后取两种子做法复杂度较小者（算是一种复杂度平衡），第一个子做法是 size 比较小的时候直接枚举 $\Delta-1$ 个三角形，然后用矩阵乘法判断是否存在最后一个三角形；第二个子做法是 size 比较大的时候先鸽笼一波排除掉一定有解的情况，然后把三角形 list 出来。
Interactive Protocals
DOES co-NP HAVE SHORT INTERACTIVE PROOFS?
Zero Knowledge Proof
看这里(Weighted) First Order Logic Model Counting and Sampling
Paul Beame, Guy Van den Broeck, Eric Gribkoff, and Dan Suciu. Symmetric Weighted First-Order Model Counting. In PODS 2015.
证明了 FO3（最多 3 个变量的一阶逻辑式子）的 WFOMC 是困难的。方法是把 $#P_1$ 问题的非确定性图灵机通过拉皮变成线性时间，然后像 Cook-Levin 定理一样归约到 FO3。
附录的一些小技巧很有用：对于 Weighted Model Counting 来说，$\exists$ 是可以去掉的（相当于只需考虑 Universal FO3），$\lnot$ 是可以去掉的，等号也是可以去掉的。这三个技巧是巧妙地使用了 weight，甚至会把代入不同的 weight 当成是多项式插值，所以 weight 版本真的不仅仅是简单加强，而是引入了更多好玩的特性。
这篇也顺带简述了 FO2 的 counting，所以是一篇很全的 WFOMC 入坑文。
Yuanhong Wang, Juhua Pu, Yuyi Wang, and Ondrej Kuzelka. On Exact Sampling in the Two-Variable Fragment of First-Order Logic. In LICS 2022.
给出了 FO2 的 WFOMS 的多项式算法。
其实 WFOMS 跟 WFOMC 的思路差不多的，因为本质上都是“用 counting 算概率来 sampling”。因此都是先处理一元谓词（1-type），再处理二元谓词（2-type）。实际上一元谓词的 1-type 可以看作是点染色，二元谓词的 2-type 可以看作是边染色。
如果是 Universal 的 WFOMS，那点染完色之后各边就独立了，那就非常简单。但现在不是 Universal，而是 Scott Normal Form，就会复杂些。但同样是把 Scott Normal Form 抽象成图论问题，变成采样一个连通图。这个图论思路非常精彩。
由于“能 counting 就能 sampling”，所以带 cardinality 限制的谓词、特殊限制谓词（比如要求一个二元谓词是一棵树）都是可以 sampling 的了。
Timothy van Bremen, and Ondrej Kuzelka. Lifted Inference with Tree Axioms. In AI 2023.
给出了特殊谓词限制（比如 tree axiom，要求谓词是一棵树）的 counting。
同样是先处理一元谓词（枚举 1-type，相当于点染色），再处理二元谓词（2-type，相当于边染色）。但是在边染色的时候，你就可以套矩阵树定理了！
头一次见到矩阵树定理在科研中的应用
这给人以一种强烈的感觉，像是我会了什么图上或树上的计数技巧（比如矩阵树定理），我就套进来，宣称我有了一种特殊谓词限制的算法。所以矩阵树定理绝不是唯一能套的，应当可以整理一个框架，讨论什么样的图上或树上计数技巧可以套进来当特殊谓词限制。
杂项
Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Venkatadheeraj Pichapati, and Ananda Theertha Suresh. Estimating the Number of Defectives with Group Testing. In ISIT 2016.
这里做的是 Group Testing 问题的其中一个版本：approximate the size of defective group，但不必求出来这个 group 具体有哪些人。
这篇文章把上界和下界都做到了 $\log \log d$，其中 $d$ 就是要预测的 size。也就是说这俩界都是紧的，这个问题算是做完了。
上界的算法就是通过不断平方、二分等方法调整预估 d 值的大小，使得 random test 结果为 1 的概率接近常数，然后用 chernoff bound 一波带走。
下界是比较 trivial 的信息论证明，究其本质就是，最终 multiplicative error approximation 其实最多只有 $\log n$ 种答案，而每次 test 只能返回 0 或 1，所以需要 $\log \log n$ 次 test 才能确定。
Nathan Linial, and Noam Nisan. Approximate Inclusion-Exclusion. In STOC 1990.
求集合并（的大小或者概率，下省略）通常用容斥转化成求集合交，如果只知道一部分集合交（具体来说，有一个参数 $k$，我们只能知道任意不超过 $k$ 个集合的交），就可以通过这个方法来近似求出集合并。
文章首先证明了任意两个集合序列，如果它们的“任意不超过 $k$ 个集合的交”都相同，这两个集合并就不会差太多。证明方法比较复杂，将“最大化集合并的差”表示成一个线性规划问题，然后对偶，变成一个求多项式的问题，再代入切比雪夫多项式。
基于这个思路也就能在线性规划那一步改一改得到一个近似算法了。
Andrew Chi-Chih Yao. Probabilistic Computations: Toward A Unified Measure of Complexity. In SFCS 1977.
著名的 Yao’s Minimax Principle。它说人话的表达就是：任意随机算法的 worst case complexity，大于等于（论文给的等于，但是 wiki 更简单的证明是大于等于）任给一个输入分布，最好的确定性算法在这上面的 complexity。
它给出了一种将随机算法 lower bound 转化成确定性算法 lower bound 的思路，就是找一个分布，使得确定性算法不能做到这个 lower bound。