2023年5月23日，前沿计算研究中心2019级本科毕业论文答辩工作顺利完成。根据信息科学技术学院的工作部署，中心有序安排本次答辩工作，中心执行主任邓小铁教授、副主任王亦洲教授、助理教授孔雨晴、姜少峰、王鹤、李彤阳、刘天任等老师作为答辩评委参加。

　　来自北京大学信息科学技术学院、元培学院、物理学院、数学科学学院的21位2019级本科生进行了毕业论文报告并顺利通过答辩，7人获评优秀毕业论文，1人获评信息科学技术学院2019级本科生“十佳”优秀毕业论文。祝贺！

A 组答辩合影

B 组答辩合影

信息科学技术学院2019级本科生“十佳”优秀毕业论文

基于几何哈希的针对高维设施选址问题的数据流算法

杨明炜，信息科学技术学院2019级图灵班

　　在欧式空间一致设施选址问题中, 输入是一个\mathbb{R}^{d}中的客户集合, 且目标是放置一些设施来服务他们, 并最小化开放设施加上连接客户的总代价。我们研究动态几何数据流的经典模型, 其中客户通过网格{1,...,Δ}^{d}中的点的插入和删除的序列给出。在我们聚焦的高维空间的情况下, 算法的空间复杂度必须与d·logΔ呈多项式相关。

　　我们给出一个基于从数据流中进行重要性采样的新算法框架, 其仅使用poly(d·logΔ)的空间来对最优代价进行近似。通过仔细地结合采样和估计的技巧, 我们成功地设计了一个O(d^1.5)-近似算法。之前的算法要么使用与d呈指数相关的空间, 要么只能保证O(d·log^2Δ)-近似。因此我们的算法在此之上进行了改进, 并首先避免了近似比中由广泛使用的四叉树分解技术所带来的O(logΔ)项。我们通过使用一个几何哈希机制实现了我们的改进。该哈希机制将\mathbb{R}^{d}中的点映射到直径有界的桶中, 且关键的的性质为任意半径足够小的点集都会被哈希到最多poly(d)个不同的桶中。

　　最后, 我们证明了即使对于只插入的数据流, 任意1.085-近似算法都需要使用与poly(d·logΔ)呈指数相关的空间。

杨明炜与论文指导老师姜少峰和同学合影

中心2019级学生本科毕业论文信息

按学生姓氏首字母排序，*为优秀毕业论文

1. 杜振宇：含噪声量子设备在计算优势上的限制

2. 韩勤：基于可泛化的神经辐射场的生产线机器人稀疏视角动态抓取姿态检测

3. 韩正一：超奇异椭圆曲线同源问题的量子算法

4. 霍子璇*：离子阱量子计算机的优化

5. 李本厚：基于视频的人体三维姿态估计技术

6. 李宁远*：同时竞赛中的参赛者均衡行为与竞赛奖项设计

7. 刘立强*：计算乘积分布统计距离的一种高效确定型算法

8. 刘雨霖*：SO(3) 流形上的归一化流

9. 楼家宁：针对聚类问题的亚线性时间算法

10. 秦杰圣：结合层次认知的群体运动预测

11. 施朱鸣：重复二价拍卖中有限预算约束动态节流机制的研究

12. 唐静吾：基于差分隐私的合成数据生成算法及其应用

13. 王逸安：基于先验信息的机器人泛化交互

14. 王颖：测试非交互式信息聚合方法中二阶信息的有效性

15. 魏罗健：一种高效的多输入门混淆方案

16. 吴越：隐私安全的去中心化扩散拍卖机制

17. 闫旭东：基于单张图片的物体形态恢复

18. 严汨*：一种基于仿真的超低成本功能性灵巧手抓取生成方法

19. 杨明炜*：基于几何哈希的针对高维设施选址问题的数据流算法

20. 叶航*：基于可驱动的隐式场的人体及服装建模

21. 尹泽楷：基于 RGB 信息和结构信息的实时机械臂-相机位姿估计