计算理论之美【2025】

本人参加了南京大学举办的 计算理论之美 2025 暑期讲习班 。总体来说，讲课内容还是相当有趣的，于是在这里挑了一部分记录了下来。本次讲习班有 7 个专题，其中次模函数没有接触过、LLM理论没咋听、分布式计算不太感兴趣，所以这几个部分没有写。其余的随机算法、哈希设计、概率集中不等式与随机数值线性代数则分别写了一些比较基本的部分。

目录

本文将仍然采用多篇的形式，本篇是全文的目录。

1. 随机算法基础

   这是NJU的计算理论之美的第一堂讲的，感觉讲的老师很强，讲的挺好的，所以简单写了一下。

2. 浅谈概率集中不等式

   这里面真的只有概率集中不等式基础，但是我确实也是第一次正经写某些 bound 。

3. 浅谈现代哈希设计

   尽管 lecture 里面其实介绍了非常现代的哈希表设计思想，但我在这里应该只会介绍一些基本的内容，主要包括 Universal Hashing 、Perfect Hashing ，以及可能的 Succinct Dictionary 。

4. 随机数值线性代数

   随机数值线性代数看起来不是一个很经典的方向，但是里面的理论还是相当有趣且深刻的，我们将会在这里介绍一些基本的内容。

   特别的，由于这是一个新兴的方向，lecture 里面的结果都是离现在较近的，且带有一定的综述性质。另外出于时间上的问题，lecture 跳过了部分引理的证明。