TCS Wiki - User contributions [en]

计算理论之美 (Summer 2026)

2026-07-27T01:06:12Z

Liumingmou: /* Tentative Schedule */

{{Infobox
|name = Infobox
|headerstyle = background:#4D72BE;
|labelstyle = background:#DAE1F0;

|header1 = 计算理论之美
|label2 = {{Nowrap|负责人}}
|data2 = 黄棱潇 ([mailto:huanglingxiao@nju.edu.cn huanglingxiao@nju.edu.cn])
|label4 = 时间
|data4 = 2026.7.24 — 2026.7.27
|label5 = 地点
|data5 = {{Nowrap|南京大学苏州校区苏教楼D202}}
|belowstyle = background:#DAE1F0;
|below =
}}

由南京大学计算机学院和智能软件学院支持的第5届“计算理论之美”暑期讲习班将于2026年7月24日至7月27日在江苏省苏州市南京大学苏州校区开班。本次讲习班将围绕算法设计主题开展系列报告，包括组合最优化、哈希表、差分隐私、量子计算、关于图的数据流算法、图计算、分布式算法等板块，主要面向对理论计算机科学以及计算机科学中的数学感兴趣的国内外本科生，安排4天的高级课程。内容深入浅出，由国内外一线的优秀学者讲授，使学员初步了解理论计算机科学的一些研究前沿、初步掌握一些新理论与新方法，为有志于从事理论计算机科学研究的学者打下一定的基础，也让从事其他相关方向研究的学生与教师们领略计算理论的魅力。

联系邮箱：nju_tcs@163.com

联系人：
* 黄棱潇： huanglingxiao@nju.edu.cn
* 刘明谋： lmm@nju.edu.cn
* 班吟： 175227530@qq.com

注册报名流程：由于前几届报名人数过多，本届将会采用问卷初筛形式进行报名。请同学们先填写以下调查问卷:

https://table.nju.edu.cn/external-apps/9ea2fbd7-8ac8-45dd-b5bf-fbdb887989be/?page_id=9UIB

问卷报名截止日期： 2026.6.20

通过初筛的同学将于讲习班开始前两周收到包含报名链接的邮件。由于今年讲习班将在苏州校区举办，南京校区的南大同学如需统一安排住宿，也请填写问卷；无需安排住宿的南大同学，'''无需填写问卷或报名，可在讲习班期间直接前往会场听取报告。'''

费用：本科生包住宿，非本科生不包含住宿。餐费自理。

'''<big>对讲习班感兴趣的九月份入学南大新生，欢迎在志愿填报完成后报名参加（发送邮箱至： nju_tcs@163.com）</big>'''

== Tentative Schedule ==

Venue (地点)：南京大学苏州校区苏教楼D202
[[File:苏教楼D.png|thumb|苏教楼D在图中红星处]]
Accommodation：南京大学苏州校区国际学术交流中心 
Group photo: 7月24日上午茶歇环节中安排参会者合影留念

Speakers (in lexicographic order): 陈林（浙江大学）、丁尧相（浙江大学）、刘明谋（南京大学）、Pasin Manurangsi（Google Research）、任瀚林（IAS）、王启圣（上海交通大学）、王宇扬(中国科学技术大学）、俞华程（普林斯顿大学）、张天翼（南京大学）、郑朝栋（南京大学）

:{|border="2" width="97%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse; empty-cells:show;"

|-
|bgcolor="#4D72BE" align="center" style="width: 21%"|'''Time'''
|bgcolor="#4D72BE" align="center"|'''Title'''
|bgcolor="#4D72BE" align="center" style="width: 40%"|'''Speaker'''

|-
|bgcolor="#DAE1F0" align="center" colspan="3"|'''7月24日 July, 24th'''

|-
|align="center"|8:30 — 12:00
|align="center"|图染色算法
|align="center"|张天翼（南京大学）

|-
|align="center" colspan="3"|12:00 — 14:00　午休

|-
|align="center"|14:00 — 17:30
|align="center"|图流算法
|align="center"|俞华程（普林斯顿大学）

|-
|bgcolor="#DAE1F0" align="center" colspan="3"|'''7月25日 July, 25th'''

|-
|align="center"|8:30 — 12:00
|align="center"|Introduction to Quantum Computation
|align="center"|王启圣（上海交通大学）

|-
|align="center" colspan="3"|12:00 — 14:00　午休

|-
|align="center"|14:00 — 17:30
|align="center"|现代哈希表设计
|align="center"|刘明谋（南京大学）
|-
|bgcolor="#DAE1F0" align="center" colspan="3"|'''7月26日 July, 26th'''

|-
|align="center"|8:30 — 12:00
|align="center"|Introduction to Differential Privacy
|align="center"|Pasin Manurangsi（Google Research）

|-
|align="center" colspan="3"|12:00 — 14:00　午休

|-
|align="center"|14:00 — 17:30
|align="center"|加性组合与算法设计
|align="center"|陈林（浙江大学）

|-
|bgcolor="#DAE1F0" align="center" colspan="3"|'''7月27日 July, 27th'''

|-
|align="center"|8:30 — 12:00
|align="center"|分布式算法与单机算法的同与异
|align="center"|郑朝栋（南京大学）

|-
|align="center" colspan="3"|12:00 — 14:00　午休

|-
|align="center"|14:00 — 15:00
|align="center"|Neuro-symbolic AI
|align="center"|戴望州（南京大学）

|-
|align="center" colspan="3"|15:00 — 15:10　休息

|-
|align="center"|15:10 — 16:10
|align="center"|Recent progress on near-maximum circuit lower bounds
|align="center"|任瀚林（Institute for Advanced Study）

|-
|align="center" colspan="3"|16:10 — 16:20　休息

|-
|align="center"|16:20 — 17:20
|align="center"|扩展图上生成树的局部计算算法
|align="center"|王宇扬（中国科学技术大学）

|-
|align="center" colspan="3"|17:20 — 17:30　交流

|}

== Take-home Exams ==
成绩优秀的同学可推荐参加南京大学计算机学院预推免保研面试，并在录取后可凭借此次暑期讲习班申请两个研究生学分。

作业提交方式：发送电子版到邮箱nju_tcs@163.com

== Getting to The Campus==
*入校：人员及车辆凭[https://tcs.nju.edu.cn/wiki/images/d/d3/%E8%AE%A1%E7%AE%97%E7%90%86%E8%AE%BA%E4%B9%8B%E7%BE%8E2026%E4%BC%9A%E8%AE%AE%E9%80%9A%E7%9F%A5.pdf 电子版会议通知]进校。
*高铁 / 动车
**苏州站：打车至校区约 30 分钟（非早晚高峰情况下），费用约 ¥30。亦可选择快线 3 号或地铁转有轨电车，全程约 2 小时。
**苏州新区站：打车至校区约 25 分钟，费用约 ¥25。也可乘坐有轨电车 2 号线，约 1 小时。
*飞机
**无锡硕放机场（WUX）：打车至校区约 30 分钟；因跨城行驶，司机可能会收取返程/空驶费用，总费用约 ¥80。如果能打到顺风车的话会较为便宜。亦可选公共交通，约 2 小时。
**上海虹桥机场（SHA）：建议从虹桥火车站换乘高铁至苏州站或苏州新区站。务必留意，由上海虹桥站前往苏州的高铁末班车时间通常是21:42。不建议从虹桥直接打车至苏州（费用较高）；同时不建议打顺风车，因为通常只能打到黑出租。

== Lunch & Supper ==
[[File:苏州校区食堂（2025）.png|thumb|苏州校区的四个食堂在图中红星处]]
* 苏州校区内现有科创大厦食堂、第16、17、18食堂共四个食堂，素菜2-3元、荤菜4-8元，可直接用支付宝或微信支付。此外，国际学术交流中心也提供更为昂贵的食物。
* 学校附近有：东渚镇、文体中心、丰茂里、时尚水岸星悦荟、星悦里等几个商业区。
* 也可以选择外卖，会送至校门口的外卖柜或外卖架上。

== Getting Around ==
* 大阳山国家森林公园 & 植物园：层林步道＋寺庙人文，爬 60–90 分钟视体力安排；秋冬晴天观景佳。
* 树山生态村：乡野步道、茶园与农家菜，团队晚餐/走读首选。
* 太湖湿地/西山方向：自驾更便捷，观湿地与湖景线。
* 古城园林：傍晚可打车去平江路/山塘街逛夜景，或白天参观苏州博物馆/拙政园。

== About Suzhou Campus ==
南京大学苏州校区位于苏州高新区太湖科技城，地处“环太湖科创圈”与“沿沪宁产业创新带”的黄金交汇点，被定位为南大发展壮大新工科的主阵地。立足“国家战略、世界一流、强强联合、需需结合”，南大苏州校区聚焦人工智能、新一代信息技术、新能源、先进制造、生命健康等领域“卡脖子”问题，强化“新工科”建设，促进文理工医交叉融合，政产学研协调发展。

== Links to Past Summer Schools ==
* [[计算理论之美 (Summer 2025)|计算理论之美暑期学校 (Summer 2025)]]
* [[计算理论之美 (Summer 2024)|计算理论之美暑期学校 (Summer 2024)]]
* [[计算理论之美 (Summer 2023)|计算理论之美暑期学校 (Summer 2023)]]
* [[计算理论之美 (Summer 2021)|计算理论之美暑期学校 (Summer 2021)]]

== About Our Summer School ==
Our summer school is supported by the School of Computer Science and the School of Intelligent Software and Engineering at Nanjing University and will be held from July 24th to July 27th, 2026, at the Suzhou Campus of Nanjing University in Suzhou, Jiangsu Province, China. The theme of this year's summer school will be the design and analysis of algorithms, with topics ranging from combinatorial optimization, hash table design, differential privacy, quantum computing, streaming algorithms for graphs, graph algorithms, and distributed algorithms.
Target audience will include aspiring undergraduate and graduate students from China and overseas, and the program will feature 4 days of advanced courses. The courses will be presented by leading young scholars both from within China and overseas, covering both cutting-edge research and modern toolkits in theoretical computer science.
The summer school will help connect aspiring young students with young scholars to engage research in theoretical computer science, and embark on a journey to appreciate the charm of computational theory.

Accommodation (shared room) will be provided to undergraduates only.

Due to capacity, we prioritize undergraduates seeking to join NJU TCS group for PhD or for a research intern. To register, please fill out the following form: https://table.nju.edu.cn/external-apps/9ea2fbd7-8ac8-45dd-b5bf-fbdb887989be/?page_id=9UIB

If you are selected into our summer school, you will receive a confirmation email.

计算理论之美 (Summer 2026)

2026-07-22T04:29:27Z

Liumingmou:

{{Infobox
|name = Infobox
|headerstyle = background:#4D72BE;
|labelstyle = background:#DAE1F0;

|header1 = 计算理论之美
|label2 = {{Nowrap|负责人}}
|data2 = 黄棱潇 ([mailto:huanglingxiao@nju.edu.cn huanglingxiao@nju.edu.cn])
|label4 = 时间
|data4 = 2026.7.24 — 2026.7.27
|label5 = 地点
|data5 = {{Nowrap|南京大学苏州校区苏教楼D202}}
|belowstyle = background:#DAE1F0;
|below =
}}

由南京大学计算机学院和智能软件学院支持的第5届“计算理论之美”暑期讲习班将于2026年7月24日至7月27日在江苏省苏州市南京大学苏州校区开班。本次讲习班将围绕算法设计主题开展系列报告，包括组合最优化、哈希表、差分隐私、量子计算、关于图的数据流算法、图计算、分布式算法等板块，主要面向对理论计算机科学以及计算机科学中的数学感兴趣的国内外本科生，安排4天的高级课程。内容深入浅出，由国内外一线的优秀学者讲授，使学员初步了解理论计算机科学的一些研究前沿、初步掌握一些新理论与新方法，为有志于从事理论计算机科学研究的学者打下一定的基础，也让从事其他相关方向研究的学生与教师们领略计算理论的魅力。

联系邮箱：nju_tcs@163.com

联系人：
* 黄棱潇： huanglingxiao@nju.edu.cn
* 刘明谋： lmm@nju.edu.cn
* 班吟： 175227530@qq.com

注册报名流程：由于前几届报名人数过多，本届将会采用问卷初筛形式进行报名。请同学们先填写以下调查问卷:

https://table.nju.edu.cn/external-apps/9ea2fbd7-8ac8-45dd-b5bf-fbdb887989be/?page_id=9UIB

问卷报名截止日期： 2026.6.20

通过初筛的同学将于讲习班开始前两周收到包含报名链接的邮件。由于今年讲习班将在苏州校区举办，南京校区的南大同学如需统一安排住宿，也请填写问卷；无需安排住宿的南大同学，'''无需填写问卷或报名，可在讲习班期间直接前往会场听取报告。'''

费用：本科生包住宿，非本科生不包含住宿。餐费自理。

'''<big>对讲习班感兴趣的九月份入学南大新生，欢迎在志愿填报完成后报名参加（发送邮箱至： nju_tcs@163.com）</big>'''

== Tentative Schedule ==

Venue (地点)：南京大学苏州校区苏教楼D202
[[File:苏教楼D.png|thumb|苏教楼D在图中红星处]]
Accommodation：南京大学苏州校区国际学术交流中心 
Group photo: 7月24日上午茶歇环节中安排参会者合影留念

Speakers (in lexicographic order): 陈林（浙江大学）、丁尧相（浙江大学）、刘明谋（南京大学）、Pasin Manurangsi（Google Research）、任瀚林（IAS）、王启圣（上海交通大学）、王宇扬(中国科学技术大学）、俞华程（普林斯顿大学）、张天翼（南京大学）、郑朝栋（南京大学）

:{|border="2" width="97%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse; empty-cells:show;"

|-
|bgcolor="#4D72BE" align="center" style="width: 21%"|'''Time'''
|bgcolor="#4D72BE" align="center"|'''Title'''
|bgcolor="#4D72BE" align="center" style="width: 40%"|'''Speaker'''

|-
|bgcolor="#DAE1F0" align="center" colspan="3"|'''7月24日 July, 24th'''

|-
|align="center"|8:30 — 12:00
|align="center"|图染色算法
|align="center"|张天翼（南京大学）

|-
|align="center" colspan="3"|12:00 — 14:00　午休

|-
|align="center"|14:00 — 17:30
|align="center"|图流算法
|align="center"|俞华程（普林斯顿大学）

|-
|bgcolor="#DAE1F0" align="center" colspan="3"|'''7月25日 July, 25th'''

|-
|align="center"|8:30 — 12:00
|align="center"|现代哈希表设计
|align="center"|刘明谋（南京大学）

|-
|align="center" colspan="3"|12:00 — 14:00　午休

|-
|align="center"|14:00 — 17:30
|align="center"|Introduction to Quantum Computation
|align="center"|王启圣（上海交通大学）

|-
|bgcolor="#DAE1F0" align="center" colspan="3"|'''7月26日 July, 26th'''

|-
|align="center"|8:30 — 12:00
|align="center"|Introduction to Differential Privacy
|align="center"|Pasin Manurangsi（Google Research）

|-
|align="center" colspan="3"|12:00 — 14:00　午休

|-
|align="center"|14:00 — 17:30
|align="center"|加性组合与算法设计
|align="center"|陈林（浙江大学）

|-
|bgcolor="#DAE1F0" align="center" colspan="3"|'''7月27日 July, 27th'''

|-
|align="center"|8:30 — 12:00
|align="center"|分布式算法与单机算法的同与异
|align="center"|郑朝栋（南京大学）

|-
|align="center" colspan="3"|12:00 — 14:00　午休

|-
|align="center"|14:00 — 15:00
|align="center"|Neuro-symbolic visual understanding, generation, and decision-making: symbolic intermediate representation matters
|align="center"|丁尧相（浙江大学）

|-
|align="center" colspan="3"|15:00 — 15:10　休息

|-
|align="center"|15:10 — 16:10
|align="center"|Recent progress on near-maximum circuit lower bounds
|align="center"|任瀚林（Institute for Advanced Study）

|-
|align="center" colspan="3"|16:10 — 16:20　休息

|-
|align="center"|16:20 — 17:20
|align="center"|扩展图上生成树的局部计算算法
|align="center"|王宇扬（中国科学技术大学）

|-
|align="center" colspan="3"|17:20 — 17:30　交流

|}

== Take-home Exams ==
成绩优秀的同学可推荐参加南京大学计算机学院预推免保研面试，并在录取后可凭借此次暑期讲习班申请两个研究生学分。

作业提交方式：发送电子版到邮箱nju_tcs@163.com

== Getting to The Campus==
*入校：人员及车辆凭[https://tcs.nju.edu.cn/wiki/images/d/d3/%E8%AE%A1%E7%AE%97%E7%90%86%E8%AE%BA%E4%B9%8B%E7%BE%8E2026%E4%BC%9A%E8%AE%AE%E9%80%9A%E7%9F%A5.pdf 电子版会议通知]进校。
*高铁 / 动车
**苏州站：打车至校区约 30 分钟（非早晚高峰情况下），费用约 ¥30。亦可选择快线 3 号或地铁转有轨电车，全程约 2 小时。
**苏州新区站：打车至校区约 25 分钟，费用约 ¥25。也可乘坐有轨电车 2 号线，约 1 小时。
*飞机
**无锡硕放机场（WUX）：打车至校区约 30 分钟；因跨城行驶，司机可能会收取返程/空驶费用，总费用约 ¥80。如果能打到顺风车的话会较为便宜。亦可选公共交通，约 2 小时。
**上海虹桥机场（SHA）：建议从虹桥火车站换乘高铁至苏州站或苏州新区站。务必留意，由上海虹桥站前往苏州的高铁末班车时间通常是21:42。不建议从虹桥直接打车至苏州（费用较高）；同时不建议打顺风车，因为通常只能打到黑出租。

== Lunch & Supper ==
[[File:苏州校区食堂（2025）.png|thumb|苏州校区的四个食堂在图中红星处]]
* 苏州校区内现有科创大厦食堂、第16、17、18食堂共四个食堂，素菜2-3元、荤菜4-8元，可直接用支付宝或微信支付。此外，国际学术交流中心也提供更为昂贵的食物。
* 学校附近有：东渚镇、文体中心、丰茂里、时尚水岸星悦荟、星悦里等几个商业区。
* 也可以选择外卖，会送至校门口的外卖柜或外卖架上。

== Getting Around ==
* 大阳山国家森林公园 & 植物园：层林步道＋寺庙人文，爬 60–90 分钟视体力安排；秋冬晴天观景佳。
* 树山生态村：乡野步道、茶园与农家菜，团队晚餐/走读首选。
* 太湖湿地/西山方向：自驾更便捷，观湿地与湖景线。
* 古城园林：傍晚可打车去平江路/山塘街逛夜景，或白天参观苏州博物馆/拙政园。

== About Suzhou Campus ==
南京大学苏州校区位于苏州高新区太湖科技城，地处“环太湖科创圈”与“沿沪宁产业创新带”的黄金交汇点，被定位为南大发展壮大新工科的主阵地。立足“国家战略、世界一流、强强联合、需需结合”，南大苏州校区聚焦人工智能、新一代信息技术、新能源、先进制造、生命健康等领域“卡脖子”问题，强化“新工科”建设，促进文理工医交叉融合，政产学研协调发展。

== Links to Past Summer Schools ==
* [[计算理论之美 (Summer 2025)|计算理论之美暑期学校 (Summer 2025)]]
* [[计算理论之美 (Summer 2024)|计算理论之美暑期学校 (Summer 2024)]]
* [[计算理论之美 (Summer 2023)|计算理论之美暑期学校 (Summer 2023)]]
* [[计算理论之美 (Summer 2021)|计算理论之美暑期学校 (Summer 2021)]]

== About Our Summer School ==
Our summer school is supported by the School of Computer Science and the School of Intelligent Software and Engineering at Nanjing University and will be held from July 24th to July 27th, 2026, at the Suzhou Campus of Nanjing University in Suzhou, Jiangsu Province, China. The theme of this year's summer school will be the design and analysis of algorithms, with topics ranging from combinatorial optimization, hash table design, differential privacy, quantum computing, streaming algorithms for graphs, graph algorithms, and distributed algorithms.
Target audience will include aspiring undergraduate and graduate students from China and overseas, and the program will feature 4 days of advanced courses. The courses will be presented by leading young scholars both from within China and overseas, covering both cutting-edge research and modern toolkits in theoretical computer science.
The summer school will help connect aspiring young students with young scholars to engage research in theoretical computer science, and embark on a journey to appreciate the charm of computational theory.

Accommodation (shared room) will be provided to undergraduates only.

Due to capacity, we prioritize undergraduates seeking to join NJU TCS group for PhD or for a research intern. To register, please fill out the following form: https://table.nju.edu.cn/external-apps/9ea2fbd7-8ac8-45dd-b5bf-fbdb887989be/?page_id=9UIB

If you are selected into our summer school, you will receive a confirmation email.

2026-06-23T15:36:24Z

Liumingmou:

计算理论之美 (Summer 2026)

2026-06-21T13:29:26Z

Liumingmou: /* Tentative Schedule */

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

2026-06-21T13:02:30Z

Liumingmou: /* Set Cover 的线性规划松弛与随机取整 */

小题均为提示性质，小题越多越简单。

== 低 <math>\ell_\infty</math>-norm 对高斯 JL 变换没有帮助==

令 <math>\Pi \in \mathbb R^{m\times d}</math> 是一个高斯 Johnson-Lindenstrauss 变换，其中每个元素独立服从 <math>N(0,1/m)</math>。给定任意固定单位向量 <math>x\in\mathbb S^{d-1}</math>。

#证明 <math>\Pi x</math> 的每个坐标都独立服从 <math>N(0,1/m)</math>。
#证明 <math>\|\Pi x\|_2^2</math> 与 <math>\frac{1}{m}\chi_m^2</math> 同分布。因此 <math>\|\Pi x\|_2</math> 的分布与 <math>\|x\|_\infty</math> 无关。
#解释为什么如果使用高斯 JL 变换，即使 <math>x</math> 满足很强的平坦性条件，例如 <math>\|x\|_\infty \le O(1/\sqrt d)</math>，为了保证 <math>\mathbb P[\|\Pi x\|_2^2-1|>\epsilon]\le \delta</math>，所需的目标维数仍然是 <math>m=\Theta(\epsilon^{-2}\log(1/\delta))</math>。
#对比坐标采样型（即 <math>\Pi x</math>直接随机输出 <math>x</math>的某几个维度）降维，简要解释为什么低 <math>\ell_\infty</math>-norm 对坐标采样有帮助，但对高斯 JL 变换没有帮助。

==torus 上的随机网格 LSH==

考虑 metric space <math>( [0,n]^d,d_{\mathrm{torus}} )</math>，其中距离定义为 <math>d_{\mathrm{torus}}(x,y)=\sqrt{\sum_{i=1}^d \min{|x_i-y_i|,n-|x_i-y_i|}^2}</math>。给定网格宽度 <math>w>0</math>。随机选择平移向量 <math>s\in[0,w)^d</math>，并定义 hash function <math>h_s(x)=(\lfloor (x_1+s_1)/w\rfloor,\dots,\lfloor (x_d+s_d)/w\rfloor)</math>，其中每个坐标都按照 torus 的方式取模。

#对于两个点 <math>x,y\in[0,n]^d</math>，记 <math>\Delta_i=\min\{|x_i-y_i|,n-|x_i-y_i|\}</math>。证明如果对所有 <math>i</math> 都有 <math>\Delta_i<w</math>，那么 <math>\mathbb P[h_s(x)=h_s(y)]=\prod_{i=1}^d (1-\Delta_i/w)</math>。
#证明如果 <math>d_{\mathrm{torus}}(x,y)\le r</math>，那么 <math>\mathbb P[h_s(x)=h_s(y)]\ge 1-\sqrt d,r/w</math>。提示：可以使用 <math>\sum_i\Delta_i\le \sqrt d\sqrt{\sum_i\Delta_i^2}</math>。
#解释为什么这个 LSH family 的随机桶可以看成随机平移后的 axis-aligned cube。请从“近点容易落在同一个随机集合中，远点不容易落在同一个随机集合中”的角度解释这个构造的直觉。
#讨论这个构造在高维空间中的局限性。特别地，当距离 <math>d_{\mathrm{torus}}(x,y)</math> 分散在很多个坐标上时，为什么随机网格更容易把 <math>x</math> 和 <math>y</math> 切开？
#设 <math>x,y</math> 只在一个坐标上相差 <math>r</math>，其他坐标完全相同。计算 <math>\mathbb P[h_s(x)=h_s(y)]</math>。
#设 <math>x,y</math> 在每个坐标上都相差 <math>r/\sqrt d</math>，因此 <math>d_{\mathrm{torus}}(x,y)=r</math>。在 <math>r/\sqrt d<w</math> 的条件下，计算 <math>\mathbb P[h_s(x)=h_s(y)]</math>，并将其写成 <math>(1-r/(w\sqrt d))^d</math> 的形式。
#比较上述两种情况。说明即使两对点的 torus 距离都等于 <math>r</math>，随机网格 LSH 的碰撞概率仍然可能不同。
#解释这说明了什么：axis-aligned grid LSH 并不是只依赖于欧氏距离的完美 LSH family，而是会受到坐标方向和维数的影响。

==球面上的随机超平面 LSH==

考虑球面空间 <math>(\mathbb S^{d-1},d)</math>，其中距离定义为 <math>d(x,y)=\arccos\langle x,y\rangle</math>。随机选择 <math>g\sim N(0,I_d)</math>，并定义 hash function <math>h_g(x)=\operatorname{sign}\langle g,x\rangle</math>。

#对任意 <math>x,y\in\mathbb S^{d-1}</math>，令 <math>\theta=\arccos\langle x,y\rangle</math>。证明 <math>\mathbb P[h_g(x)=h_g(y)]=1-\theta/\pi</math>。
#解释上述公式的几何直觉：随机超平面什么时候会把 <math>x</math> 和 <math>y</math> 分到两侧？
#现在使用 <math>k</math> 个独立随机超平面 <math>g_1,\dots,g_k</math>，并定义组合 hash key 为 <math>H(x)=(h_{g_1}(x),\dots,h_{g_k}(x))</math>。证明 <math>\mathbb P[H(x)=H(y)]=(1-\theta/\pi)^k</math>。
#给定两个角度阈值 <math>0<\theta_1<\theta_2<\pi</math>。令近点满足 <math>d(x,y)\le \theta_1</math>，远点满足 <math>d(x,y)\ge \theta_2</math>。写出这个 LSH family 的参数 <math>p_1</math> 和 <math>p_2</math>，并推导标准 LSH exponent <math>\rho=\log(1/p_1)/\log(1/p_2)</math>。

==由范数保持推出内积保持==

设线性映射 <math>\Pi</math> 对向量集合 <math>{x,y,x+y,x-y}</math> 都保持平方范数，即对所有 <math>v\in{x,y,x+y,x-y}</math> 都有 <math>(1-\epsilon)\|v\|_2^2\le \|\Pi v\|_2^2\le (1+\epsilon)\|v\|_2^2</math>。

#使用恒等式 <math>\langle x,y\rangle=(\|x+y\|_2^2-\|x-y\|_2^2)/4</math>，证明 <math>|\langle \Pi x,\Pi y\rangle-\langle x,y\rangle|\le O(\epsilon)(\|x\|_2^2+\|y\|_2^2)</math>。
# 在 <math>\|x\|_2=\|y\|_2=1</math> 的情况下，将上式化简为 <math>|\langle \Pi x,\Pi y\rangle-\langle x,y\rangle|\le O(\epsilon)</math>。
# 解释为什么如果 JL 变换对 <math>n</math> 个点的所有两两距离都近似保持，那么这些点的两两内积也近似保持。
# 进一步讨论：如果这些点都在单位球面上，那么 JL 降维之后，球面角度 <math>\arccos\langle x,y\rangle</math> 在什么意义下也被近似保持？

==从阈值版 Approximate Near Neighbor 到 Approximate Nearest Neighbor==

假设你有一个阈值版 Approximate Near Neighbor 黑盒。给定半径 <math>r</math> 和查询点 <math>q</math>，如果数据集 <math>P</math> 中存在点 <math>p</math> 满足 <math>|p-q|\le r</math>，那么黑盒会返回某个点 <math>p'</math>，并保证 <math>|p'-q|\le a r</math>。

现在希望用这个黑盒解决普通 Approximate Nearest Neighbor 问题。设真正最近邻距离为 <math>d^\star=\min_{p\in P}|p-q|</math>。我们建立一组半径 <math>r_0,r_1,r_2,\dots</math>，满足 <math>r_{i+1}=b r_i</math>。查询时，从小到大尝试这些半径，并返回第一个成功的黑盒查询结果。

#证明最终得到的近似比至多为 <math>ab</math>。
#如果希望最终得到 <math>c</math>-approximate nearest neighbor，应该如何选择 <math>a</math> 和 <math>b</math>？
#解释为什么常见做法中，会把阈值版 ANN 黑盒的 approximate ratio 从 <math>c</math> 设置为 <math>\sqrt c</math>。
#如果最近邻距离的可能范围被限制在 <math>[1,\Delta]</math> 中，分析需要建立多少个半径层级。

==先用 JL 降维，再做随机超平面 LSH==

设 <math>P\subseteq\mathbb S^{d-1}</math> 是 <math>n</math> 个单位向量。令 <math>\Pi:\mathbb R^d\to\mathbb R^m</math> 是一个 JL transform，并假设对所有 <math>x,y\in P</math>，都有 <math>\left|\|\Pi x-\Pi y\|_2^2-\|x-y\|_2^2\right|\le \epsilon</math>。同时假设对所有 <math>x\in P</math>，都有 <math>\left|\|\Pi x\|_2^2-1\right|\le \epsilon</math>。

#证明对所有 <math>x,y\in P</math>，都有 <math>|\langle \Pi x,\Pi y\rangle-\langle x,y\rangle|\le O(\epsilon)</math>。
#令 <math>\theta=\arccos\langle x,y\rangle</math>，并令 <math>\widetilde\theta=\arccos(\langle \Pi x,\Pi y\rangle/(\|\Pi x\|_2\|\Pi y\|_2))</math>。在 <math>\theta</math> 不太接近 <math>0</math> 或 <math>\pi</math> 的情况下，给出 <math>|\theta-\widetilde\theta|</math> 的上界。
#解释为什么可以先对数据集 <math>P</math> 做 JL 降维，再在低维空间中使用随机超平面 LSH。
#讨论当两个点的夹角非常小时，为什么需要更小的 JL 误差才能保证角度的相对误差较好。

==为什么 CountSketch 需要随机符号==

考虑一个没有随机符号的 CountSketch。对每个 <math>i\in[n]</math>，随机选择桶 <math>h(i)\in[m]</math>，并令 <math>\Pi_{h(i),i}=1</math>，其他位置为 <math>0</math>。
取向量 <math>x=(1,1,\dots,1)/\sqrt n</math>。

#证明 <math>\mathbb E\|\Pi x\|_2^2=1+(n-1)/m</math>。
#说明如果 <math>m=o(n)</math>，那么这个没有随机符号的 sketch 对该向量的范数估计会有严重偏差。
#现在考虑标准 CountSketch：对每个 <math>i\in[n]</math>，随机选择桶 <math>h(i)\in[m]</math>，并随机选择符号 <math>\sigma_i\in\{-1,1\}</math>，令 <math>\Pi_{h(i),i}=\sigma_i</math>，其他位置为 <math>0</math>。解释随机符号 <math>\sigma_i</math> 如何使不同坐标碰撞产生的交叉项在期望中相互抵消。
#总结随机符号在 CountSketch 中的作用：它并不能避免碰撞，但可以让碰撞带来的误差成为均值为零的随机噪声。

==CountSketch OSE 的 <math>m=\Omega(d^2)</math> 下界==

假设 <math>n\gg d</math>（不妨假设 <math>n>2^d</math>）。考虑使用一个 column sparsity 只有 <math>1</math> （即，每一列只有一个非零元素）的矩阵 <math>\Pi\in\mathbb R^{m\times n}</math> 进行 Oblivious Subspace Embedding (OSE)。考虑这样的'''随机'''矩阵 <math>A\in \{0,1\}^{n\times d}</math>： <math>A</math> 的每一列随机选择一个位置为 <math>1</math>，其他位置为 <math>0</math>。尝试证明，任意'''确定'''的 <math>\Pi</math> 为<math>A</math>的列空间进行子空间嵌入都至少需要 <math>m=\Omega(d^2)</math> ，即它作为 OSE 不可能降维到 <math>o(d^2)</math>。提示：尝试观察 <math>\Pi Ae_i, \Pi A(e_i+e_j)</math> 的 <math>\ell_2</math>-norm，以及你可能需要应用 birthday paradox（随机地把 <math>d</math> 个球丢入 <math>m</math> 个桶中，那么要满足 <math>m=\Omega(d^2)</math> 才能使得有 <math>\Omega(1)</math>的概率，这 <math>d</math> 个球中不会有两个球被丢进了同一个桶中）。

==CountSketch OSE 的 <math>m=O(d^2/\epsilon^2\delta)</math> 上界==

令 <math>U\in\mathbb R^{n\times d}</math> 是一个列正交矩阵，即 <math>U^\top U=I_d</math>。令 <math>\Pi\in\mathbb R^{m\times n}</math> 是 CountSketch 矩阵：对每个原始坐标 <math>i\in[n]</math>，随机选择桶 <math>h(i)\in[m]</math>，并随机选择符号 <math>\sigma_i\in\{-1,1\}</math>；然后令 <math>\Pi_{h(i),i}=\sigma_i</math>，其他位置为 <math>0</math>。记 <math>u_i</math> 为 <math>U</math> 的第 <math>i</math> 行，视为 <math>\mathbb R^d</math> 中的列向量。

#证明 <math>\Pi^\top\Pi-I_n</math> 的第 <math>(i,j)</math> 个元素在 <math>i\ne j</math> 时等于 <math>\mathbf 1_{h(i)=h(j)}\sigma_i\sigma_j</math>，在 <math>i=j</math> 时等于 <math>0</math>。
#推出 <math>U^\top\Pi^\top\Pi U-I_d=\sum_{i\ne j:h(i)=h(j)}\sigma_i\sigma_j u_i u_j^\top</math>。
#证明在计算 <math>\mathbb E[\|U^\top\Pi^\top\Pi U-I_d\|_F^2]</math> 时，随机符号会使所有交叉项的期望为 <math>0</math>。也就是说，只有同一对 <math>(i,j)</math> 与自身相乘的项会保留下来。
#证明 <math>\mathbb E[\|U^\top\Pi^\top\Pi U-I_d\|_F^2]\le \frac{1}{m}\sum_{i\ne j}|u_i|_2^2|u_j|_2^2</math>。
#使用 <math>\sum_i|u_i|_2^2=|U|_F^2=d</math>，证明 <math>\mathbb E[|U^\top\Pi^\top\Pi U-I_d|_F^2]\le d^2/m</math>。
#用 Markov 不等式证明，如果 <math>m\ge d^2/(\epsilon^2\delta)</math>，那么以概率至少 <math>1-\delta</math>，有 <math>\|U^\top\Pi^\top\Pi U-I_d\|_F\le \epsilon</math>。
#证明如果 <math>\|U^\top\Pi^\top\Pi U-I_d\|_2\le \epsilon</math>，那么对所有 <math>x\in\mathbb R^d</math> 都有 <math>(1-\epsilon)\|Ux\|_2^2\le \|\Pi Ux\|_2^2\le (1+\epsilon)\|Ux\|_2^2</math>。并解释为什么第 (6) 问中的 Frobenius norm bound 足以推出 spectral norm bound。
#总结：说明 CountSketch 虽然每一列只有一个非零元素，但当 <math>m=O(d^2/(\epsilon^2\delta))</math> 时，仍然可以作为一个 <math>d</math> 维子空间的 Oblivious Subspace Embedding。
== 点容量最大流 ==

在通常的最大流问题中，每条边有容量限制。现在考虑如下变体：图为有向图 <math>G=(V,E)</math>，源点为 <math>s</math>，汇点为 <math>t</math>。每条边的容量均为无穷大，但每个点 <math>v\in V</math> 有容量限制 <math>c_v</math>，表示流经该点的总流量不能超过 <math>c_v</math>。可以假设 <math>s</math> 和 <math>t</math> 没有点容量限制，或者它们的点容量为无穷大。

请设计一个多项式时间算法，求从 <math>s</math> 到 <math>t</math> 的最大可行流量。请清楚说明你的建图方式，并证明你的算法是正确的。

== 二分图最大匹配与最小点覆盖的线性规划 ==

令 <math>G=(L,R,E)</math> 是一个二分图。

请写出最大匹配问题的整数规划，并写出它的线性规划松弛。请进一步写出该线性规划的对偶问题。

请写出最小点覆盖问题的整数规划，并说明它与上述对偶线性规划之间的关系。

最后，请利用线性规划对偶性以及二分图匹配问题的整数性，证明二分图中的最大匹配大小等于最小点覆盖大小。也就是说，证明 <math>\nu(G)=\tau(G)</math>，其中 <math>\nu(G)</math> 表示最大匹配大小，<math>\tau(G)</math> 表示最小点覆盖大小。

== 背包问题的线性规划松弛与取整 ==

考虑 <math>0</math>-<math>1</math> 背包问题。有 <math>n</math> 个物品，第 <math>i</math> 个物品的价值为 <math>v_i</math>，重量为 <math>w_i</math>，背包容量为 <math>C</math>。目标是在总重量不超过 <math>C</math> 的前提下最大化总价值。

请写出该问题的整数规划，并写出它的线性规划松弛。

请设计一个基于线性规划松弛最优解的取整算法，得到一个整数可行解。请证明你的算法的近似比。也就是说，请证明你的算法得到的解的价值至少是最优整数解价值的某个常数比例。

== 带下界的可行流 ==

给定一个有向网络 <math>G=(V,E)</math>。每条边 <math>e\in E</math> 有流量下界 <math>\ell_e</math> 和流量上界 <math>u_e</math>，其中 <math>0\le \ell_e\le u_e</math>。我们希望判断是否存在一个流 <math>f</math>，使得每条边都满足 <math>\ell_e\le f_e\le u_e</math>，并且每个点都满足流量守恒。

请设计一个多项式时间算法判断这样的可行流是否存在。如果存在，请说明如何构造一个可行流。请证明你的算法是正确的。

== DAG 最小路径覆盖 ==

给定一个有向无环图 <math>G=(V,E)</math>。一个路径覆盖是若干条有向路径的集合，使得每个点 <math>v\in V</math> 恰好出现在其中一条路径中。路径可以只包含单个点。

请设计一个多项式时间算法，求 <math>G</math> 的最小路径覆盖大小。

请将该问题归约为二分图最大匹配问题。设归约后得到的二分图的最大匹配大小为 <math>M</math>，请证明原图的最小路径覆盖大小为 <math>|V|-M</math>。

== 点不相交路径 ==

给定一个有向图 <math>G=(V,E)</math> 和两个不同的点 <math>s,t\in V</math>。我们希望找到尽可能多条从 <math>s</math> 到 <math>t</math> 的路径，使得任意两条路径除了端点 <math>s</math> 和 <math>t</math> 以外不共享任何内部点。

请设计一个多项式时间算法，求最多有多少条两两内部点不相交的 <math>s</math>-<math>t</math> 路径。请证明你的算法是正确的。

== 带权点覆盖的 Primal-Dual 算法 ==

给定一个无向图 <math>G=(V,E)</math>，每个点 <math>v\in V</math> 有非负权重 <math>w_v</math>。带权点覆盖问题要求选择一个点集 <math>C\subseteq V</math>，使得每条边至少有一个端点属于 <math>C</math>，并最小化 <math>\sum_{v\in C} w_v</math>。

请写出该问题的整数规划和线性规划松弛。请写出该线性规划松弛的对偶问题。

请基于 primal-dual schema 设计一个 <math>2</math>-approximation 算法，并证明其近似比。你的证明应当说明算法构造的对偶解为什么可行，以及输出的点覆盖的权重为什么至多为对偶目标值的 <math>2</math> 倍。

== Set Cover 的线性规划松弛与随机取整 ==

给定一个全集 <math>U</math> 和集合族 <math>\mathcal S</math>，其中每个集合 <math>S\in\mathcal S</math> 有非负成本 <math>c_S</math>。Set Cover 问题要求选择若干集合，使得 <math>U</math> 中每个元素都被至少一个被选集合覆盖，并最小化被选集合的总成本。

请写出 Set Cover 的整数规划和线性规划松弛。设线性规划松弛的最优解为 <math>x_S</math>。

考虑如下随机取整算法：令 <math>\alpha>0</math>，并对每个集合 <math>S\in\mathcal S</math>，独立地以概率 <math>x'_S=\min\{1,\alpha x_S\}</math> 选择集合 <math>S</math>。

请证明当 <math>\alpha=\Theta(\log |U|)</math> 时，所有元素以高概率都被覆盖。请进一步分析该算法的期望成本，并证明它给出一个 <math>O(\log |U|)</math>-approximation。

== 带点容量和需求的最小费用运输问题 ==

有若干工厂、仓库和商店。工厂可以生产货物，商店有固定需求，货物可以通过若干运输边从工厂经过仓库运送到商店。每条运输边 <math>e</math> 有容量上界 <math>u_e</math> 和单位运输费用 <math>a_e</math>。每个仓库 <math>v</math> 有吞吐能力限制 <math>c_v</math>，表示通过该仓库的总货物流量不能超过 <math>c_v</math>。每个工厂 <math>i</math> 的供应上限为 <math>s_i</math>，每个商店 <math>j</math> 的需求量为 <math>d_j</math>。

请设计一个最小费用流模型，判断是否存在满足所有商店需求的运输方案，并在存在时求出最小总运输成本。请说明如何在网络中表示工厂供应、商店需求、运输边容量与费用，以及仓库的点容量限制。请证明你的模型与原问题等价。

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

2026-06-21T13:00:40Z

2026-06-05T18:16:56Z

Liumingmou: /* 课后作业 */

{{Infobox
|name = Infobox
|bodystyle =
|title = 高级算法
 Advanced Algorithms
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =任课教师
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = '''刘明谋'''
|header3 =
|label3 = 电子邮件
|data3 = lmm@nju.edu.cn
|header4 =
|label4= 办公室
|data4= 南雍-西229
|header5 =
|label5 =
|header11 = 课程时间地点
|label11 =
|data11 =
|header12 =
|label12 = 教室
|data12 = 周一，9am-12pm 苏教B207
|header13 =
|label13 = Place
|data13 =
|header14 =
|label14 = 答疑时间
|data14 = 周五，2pm-5pm 南雍-西229
|header15 = 教材
|label15 =
|data15 =
|header16 =
|label16 =
|data16 = [[File:MR-randomized-algorithms.png|border|100px]]
|header17 =
|label17 =
|data17 = Motwani and Raghavan. ''Randomized Algorithms''. Cambridge Univ Press, 1995.
|header18 =
|label18 =
|data18 = [[File:Approximation_Algorithms.jpg|border|100px]]
|header19 =
|label19 =
|data19 = Vazirani. ''Approximation Algorithms''. Springer-Verlag, 2001.
|belowstyle = background:#ddf;
|below =
}}

This is the webpage for the ''Advanced Algorithms'' class of spring 2026. Students who take this class should check this page periodically for content updates and new announcements.

= 通知 =

* '''(2026/3/2)''' 第一堂课
* '''(2026/3/23)''' 请大家'''严格遵守[https://jw.nju.edu.cn/_upload/article/files/ab/85/1f49e9e9434dbf23018539b4c338/a550b349-9828-4a05-a5ec-d088b442bee1.pdf 《关于本科生规范使用生成式人工智能工具的指导意见（试行）》]'''！
* '''(2026/4/6)''' 是清明节假期，停课一次。
* '''(2026/5/3)''' Feistel cipher / Feistel permutation 的正确定义是 <math>(x_1,x_2) \mapsto (f(x_2)\oplus x_1,x_2)</math>。第二次作业原本的题面写错了。
* '''(2026/5/4)''' 是五一假期，停课一次。
* '''(2026/5/11)''' 第一节课（9am-10am）期中考试
* '''(2026/6/1)''' 老师出差，停课一次

= 课程信息 =
* '''任课教师''':
:* [https://liumingmou.github.io 刘明谋]：[mailto:lmm@nju.edu.cn 📧]，南雍-西229
* '''助教''':
** 王思齐：[mailto:siqi_wang@smail.nju.edu.cn 📧]
** 齐世毅：[mailto:1083951258@qq.com 📧]
* '''课程时间地点''':
** 周一，9am-12pm，苏教B207
* '''答疑时间''': 周五, 2pm-5pm, 南雍-西229
* '''QQ群''': 1083465754

= 教学大纲 =
随着计算机算法理论的不断发展，现代计算机算法的设计与分析大量地使用非初等的数学工具以及非传统的算法思想。“高级算法”这门课程就是面向计算机算法的这一发展趋势而设立的。课程将针对传统算法课程未系统涉及、却在计算机科学各领域的科研和实践中扮演重要角色的高等算法设计思想和算法分析工具进行系统讲授。

课程内容分为五大部分：
* 基于哈希的大数据算法
* 哈希表与面向大数据的现代计算场景
* 测度的集中与处理高维数据
* 最大流与线性规划
* 其他重要话题

=== 先修课程 ===
* 必须：离散数学，概率论，线性代数。
* 推荐：算法设计与分析。

=== 课程教材 ===
本门课较为前沿，大部分课程内容还没有进入任何教材。以下教材和参考书仅作为参考。
* [[高级算法 (Fall 2024) / Course materials|教材和参考书]]
更多的内容也可以参考[[#Related_Online_Courses |其他学者的同类课程]]。

=== 成绩 ===
* 课程成绩：本课程将会有若干次作业和一次期末考核。最终成绩将由平时作业成绩和期末考核成绩综合得出。
* 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

=== 学术诚信 Academic Integrity ===
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。

作业完成的原则：'''署你名字的工作必须是你个人的贡献，任何不是由你完成的部分都必须明确标注'''，特别是由AI生成的部分，否则就涉嫌抄袭。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。符合规则的讨论与致谢将不会影响得分。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。

= 课后作业 =
Late policy: In general, we will accomodate late submission requests ONLY IF you made such requests ahead of time.

请大家'''严格遵守[https://jw.nju.edu.cn/_upload/article/files/ab/85/1f49e9e9434dbf23018539b4c338/a550b349-9828-4a05-a5ec-d088b442bee1.pdf 《关于本科生规范使用生成式人工智能工具的指导意见（试行）》]'''！

（如果你提交过作业之后想重新提交，可以通过更改“版本”字段换一个文件名提交）
*[[高级算法_(Spring_2026)/作业1|作业1]] 请在 2026/04/06 上课前（9am UTC+8）上传到 [https://box.nju.edu.cn/u/d/628bff0686e14f8cbf3f/ 南大云盘] (文件名为'学号_姓名_版本.pdf').
*[[高级算法_(Spring_2026)/作业2|作业2]] 请在 2026/05/11 上课前（9am UTC+8）上传到 [https://box.nju.edu.cn/u/d/475a895457d14d31ab24/ 南大云盘] (文件名为'学号_姓名_版本.pdf')。

*[[高级算法_(Spring_2026)/大作业|大作业]]。 DDL：TBA

= 课件及相关阅读资料 =
# [https://box.nju.edu.cn/f/980d814e4ad64285a640/ Fingerprinting]
#* Polynomial Identity Testing
#* Communication Complexity (Equality)
#* Application: Bipartite Perfect Matching, Checking Matrix Multiplication
#* Karp-Rabin Algorithm (string-searching), Lipton’s Algorithm (checking identity of multisets)
# [https://box.nju.edu.cn/f/fcf9e2b3051e443fb324/ Sketching]
#* Morris' Algorithm
#** mean trick, median trick
#* Counting Distinct Elements: min sketch, Flajolet-Martin algorithm, bottom-<math>k</math> algorithm, HyperLogLog
#* Heavy Hitter & Point Query: count-min sketch
#* 2nd Frequency Moments Estimator: count sketch
#** <math>\ell_2</math> point query with count sketch
#* Approximate Membership: Bloom filter
# [https://box.nju.edu.cn/f/40f8ae1bc97c409aa485/ Hashing]
#* Load Balancing: maximum load, power of two choices
#* Perfect Hashing: birthday paradox, FKS perfect hashing
#* Modern Hash Table: Cuckoo hashing, succinct dictionaries
#* Hashing in Practice: Chernoff Bound with limited independence, tabulation hashing
# [https://box.nju.edu.cn/f/c44c13910eff43ffaf7f/ Dimensionality reduction]
#* Johnson-Lindenstrauss Transformation:
#** Intuition: In high-dimensional spaces, a uniformly random vector is almost certainly nearly orthogonal to any fixed vector
#** Constructions: independent Gaussian entries, projection onto uniform random subspace, i.i.d. -1/+1 entries
#** Modern applications: TurboQuant versus RaBitQ versus Quantized JL
#** Fast Johnson-Lindenstrauss Transformation
#* Approximate Nearest Neighbor Search: by dimensionality reduction, by Locality Sensitive Hashing (LSH)
#* Oblivious Subspace Embedding (OSE): net argument
#** Application: linear regression by sketch-and-solve via OSE, linear regression by fast iteration with OSE
#** Sparse Oblivious Subspace Embedding: count sketch

= Related Online Courses=
* [https://www.cs.columbia.edu/~andoni/advancedS24/index.html Advanced Algorithms] by Alexandr Andoni at Columbia University.
* [https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15854-f21/www/ Advanced Approximation Algorithms] by Anupam Gupta at CMU.
* [http://people.csail.mit.edu/moitra/854.html Advanced Algorithms] by Ankur Moitra at MIT.
* [https://6.5210.csail.mit.edu/ Advanced Algorithms] by David Karger at MIT.
* [https://www.cs.cmu.edu/~dwoodruf/teaching/15851-spring24/ Algorithms for Big Data] by David Woodruff at CMU.
* [https://www.sketchingbigdata.org/fall20/lec/ Sketching Algorithms] by Jelani Nelson at UC Berkeley.
* [http://web.stanford.edu/class/cs168/index.html The Modern Algorithmic Toolbox] by Tim Roughgarden and Gregory Valiant at Stanford.
* [https://www.cs.princeton.edu/courses/archive/fall18/cos521/ Advanced Algorithm Design] by Pravesh Kothari and Christopher Musco at Princeton.
* [http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/ Linear and Semidefinite Programming (Advanced Algorithms)] by Anupam Gupta and Ryan O'Donnell at CMU.
* [https://www.cs.cmu.edu/~odonnell/papers/cs-theory-toolkit-lecture-notes.pdf CS Theory Toolkit] by Ryan O'Donnell at CMU.
* [https://cs.uwaterloo.ca/~lapchi/cs860/index.html Eigenvalues and Polynomials] by Lap Chi Lau at University of Waterloo.

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

2026-06-05T18:11:54Z

Liumingmou:

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

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

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