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

至多四人一组，从以下论文中选择一篇，撰写一篇 review，中英文不限。你需要尽可能详细地解释：该论文解决了什么问题，该问题为什么重要（或者提出了什么技术，该技术为什么重要），该问题有什么相关研究（包括该论文提到的，和没提到的，以及在该论文发表之后的新的相关研究），为了解决该问题该论文提出了什么技术，该技术背后的直觉是什么，该技术有什么非凡之处厉害之处，最后尽可能详细地（以一个挑剔严谨的、没有读过该论文的同学可以通过阅读你的 review 来轻松地弄明白、来轻松地验证为标准）解释该技术是如何实现的，如何证明该技术的正确性和优越性。

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. Unifying the Landscape of Cell-Probe Lower Bounds
12. Optimal Space Lower Bounds for all Frequency Moments
13. Tight Lower Bounds for the Distinct Elements Problem
14. On the Cell Probe Complexity of Dynamic Membership
15. External Memory Priority Queues with Decrease-Key and Applications to Graph Algorithms
16. An Improved Distributed Algorithm for Maximal Independent Set
17. Breaking the [math]\displaystyle{ O(n^2) }[/math] bit barrier: Scalable byzantine agreement with an adaptive adversary
18. Simple Contention Resolution via Multiplicative Weight Updates
19. Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps
20. What Cannot Be Computed Locally!
21. Impossibility of Distributed Consensus with One Faulty Process

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