高级算法 (Spring 2026)/大作业

• 至多四人一组，从以下论文中选择一篇，撰写一篇 review，中英文不限。
  • 你需要尽可能详细地解释：该论文解决了什么问题，该问题为什么重要（或者提出了什么技术，该技术为什么重要），该问题有什么相关研究（包括该论文提到的，和没提到的，以及在该论文发表之后的新的相关研究），为了解决该问题该论文提出了什么技术，该技术背后的直觉是什么，该技术有什么非凡之处厉害之处。
  • 最后尽可能详细地（以一个挑剔严谨的、没有读过该论文的同学可以通过阅读你的 review 来轻松地弄明白、来轻松地验证为标准）解释该技术是如何实现的，如何证明该技术的正确性和优越性。
• 结果分数30%，过程分数70%. 必须使用 Notion / Overleaf / Google Docs / Word Online / Github 等在线的有版本历史的工具。(如需使用 overleaf student plan 这样的付费服务可以向老师申请，老师予以报销。 notion education plus 是免费的。）
  • 教师和助教应能够看到论文从资料收集、逐渐理解、观点形成、草稿撰写到反复修改的过程。如果记录不完整会扣除过程分。没有记录视为作弊。不接受截止日前一次性上传完整论文作为有效过程记录。
  • 必须开放可以随时在线访问的版本历史供教师或助教检查，老师会在你们撰写的过程中偶尔查看你们的进展。
  • 小组成员尽量保留阅读笔记、草稿和修改记录，需在版本历史记录中设法留下各自贡献的痕迹。
  • 有不懂的地方允许咨询AI帮助理解，或者求助AI帮助查询信息，但是不接受AI代写。需将AI使用记录放入版本历史中一并以可追溯的方式提交。你有责任验证AI告诉你的事情的真伪，不接受“AI是这么说的”作为借口。
  • 教师或助教可能在提交后随机抽取小组进行口头检查。每位成员都需要解释自己负责的内容、论文的核心论点、主要参考文献、修改过程以及 AI 工具的使用情况。若学生无法解释提交内容，或过程记录与最终文本严重不符，将被视为学术诚信风险，并影响成绩。

1. Succinct dynamic dictionaries and trees
2. On Data Structures and Asymmetric Communication Complexity
3. A Hash Table Without Hash Functions, and How to Get the Most Out of Your Random Bits
4. Lower bounds on Locality Sensitive Hashing （很短，但是你需要解释其中的傅里叶分析）
5. Data structures meet cryptography: 3SUM with preprocessing
6. Optimal resizable arrays
7. Tiny Pointers
8. How to Approximate A Set Without Knowing Its Size In Advance
9. Succinct Filters for Sets of Unknown Sizes
10. Succincter. M Patrascu. 2008
11. Changing base without losing space
12. Unifying the Landscape of Cell-Probe Lower Bounds
13. Optimal Space Lower Bounds for all Frequency Moments
14. Tight Lower Bounds for the Distinct Elements Problem
15. On the Cell Probe Complexity of Dynamic Membership
16. External Memory Priority Queues with Decrease-Key and Applications to Graph Algorithms
17. An Improved Distributed Algorithm for Maximal Independent Set
18. Breaking the [math]\displaystyle{ O(n^2) }[/math] bit barrier: Scalable byzantine agreement with an adaptive adversary
19. Simple Contention Resolution via Multiplicative Weight Updates
20. Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps
21. What Cannot Be Computed Locally!
22. Impossibility of Distributed Consensus with One Faulty Process

• 获取论文原文也是作业的一部分。
• 需要在review中注明参与完成 review 的每个同学的贡献。
• 到南大表格填写表格来认领论文。
• 有问题可以问老师或者助教。