【阅读计划】一些看上去很有意思的文献
这是许多我只瞥了一眼但是觉得很有趣的文章的大集合，
本文不断更新or删除。
看上去是一个很新很有趣的加密技术。
拍卖中的胜者往往很懊悔自己多掏钱了，叫做cursed（被诅咒的）。这篇文章似乎在讲怎样在cursed情况下让顾客满意。
协议理论里有个概念叫unbeatability，看上去是个蛮有意思的东西。
Strategyproofness-Exposing Mechanism Descriptions
似乎在探索机制设计的一个新方向——我已经有一个机制了，怎么向玩家描述这个机制？
用零知识证明的方法来承诺机制设计中的一些东西。
上面这三篇都是 Yannai Gonczarowski 的文章，这个人做的研究好像都蛮有意思的。这个人本身很就很有趣，不仅是理论计算机科学家，还是个优秀的男中音歌唱家。
On the Hardness of Dominant Strategy Mechanism Design
一般性地研究了组合拍卖中实施占优策略的通信复杂性
Languages That Capture Complexity Classes
一篇奠基性的老文，介绍了P vs NP问题如何等价于数理逻辑和证明论中的一个问题的，关联起了P vs NP和数学基础。
研究了潘多拉盒子问题的委派效率缺口，提出了好多Open problems，看上去很有趣。
On the Efficiency of An Election Game of Two or More Parties: How Bad Can It Be?
研究了多党选举相比两党选举的效率缺陷。
Commitment Schemes and Zero-Knowledge Protocols
对承诺框架和零知识协议的小综述。
Simplified Prophet Inequalities for Combinatorial Auctions
组合拍卖中简化的先知不等式，应该是SOSA上的。
Knuth奖得主 Oded Goldreich 先生对P=BPP的畅想。
刊登于1977年的《物理》杂志的旧文，是一篇科学哲学论文，这位老一辈同志对相对论的认识非常深刻，把单程光速不可测引出的几乎所有问题都阐释了一遍。
Quantum Theory From Five Reasonable Axioms
量子力学的公理化尝试，作者试图用5条公理描述整个量子力学的基础。
Quantum Computing since Democritus
Scott Aaronson的知名作品，以前是作为一门课来讲的。从题目可以预见到是一个有趣、广博但可能组织稍许杂乱（这类书的通病）的作品。
每个关于P vs NP的科普都喜欢提一嘴——蛋白质折叠问题是NP完全问题，以表现P vs NP问题的紧要性。但究竟这是什么意思？这两篇文章就是蛋白质折叠复杂性分析的开山之作（从文献意义上讲），分别来自1993年的 Aviezri S. Fraenkel; Ron Unger 和 John Moult。这两篇文章出现在同一份期刊的同一卷，同时出现了奇特的两篇文献互相引用的情况。另外，这两篇文章都宣称 Fraenkel 1990年就在魏茨曼科学研究所的一场名为Deexponentializing complex computational mathematical problems using physical and biological systems的报告中给出了“2维蛋白质折叠预测是NP完全问题”的结果。这场报告从名字上看也很有意思，即想要通过物理和生物的模拟计算来将一些问题去指数化。恰好我还看到下面这样一篇文献。
The Complexity of Analog Computation
模拟计算这几年因为人工智能的发展又迎来一股热潮，有不少初创公司都瞄准了“模拟芯片”研发，原因就是人工智能的“模糊性”、大量的参数变动、各类实值运算，都和模拟计算机的性质非常匹配。模拟计算似乎能快速解决一些数字计算机难以解决的问题，但是它们真的有本质的不同吗？这篇1986年的文章推广了丘奇-图灵论题，阐明了模拟计算和数字计算的联系，证明了模拟计算同样无法突破P vs NP的牢笼。