本周日（10月17日）晚上19:30，学堂112，张辰逸、岑若虚同学会分享自己的工作，时长约为一到两小时。
张辰逸：Classical and quantum algorithms for escaping from saddle points
张辰逸是姚班2018级（计科80）本科生，本次 seminar 他将介绍他在量子优化算法方面的工作。给定一个 R^n 上的光滑函数，允许你在不同位置处查询函数值和梯度。你最少用多少次询问，可以找到一个局部最小值点？在经典计算机上，之前最好的算法需要 Õ(log^6(n)/ε^1.75) 次查询才能找到一个ε-近似的二阶局部最小值点。张辰逸同学将介绍自己的新工作 —— 在经典计算机上，他们提出的新算法仅需 Õ(log(n)/ε^1.75) 次查询；而在量子计算机上，Õ(log^2(n)/ε^1.75) 次查询即可，甚至不需要查询梯度信息。
岑若虚：Minimum Cuts in Directed Graphs via Partial Sparsification
岑若虚是姚班2015级（计科50）毕业生，现为杜克大学一年级博士生。本次seminar他将介绍他在图论算法方面的研究。最小割问题是图论中的经典问题，研究的是如何将一个图分成两部分，使得跨越不同部分的边权之和最小。对于 n 个点 m 条边的带权有向图，岑若虚及其合作者提出了一个新的算法，只需要 Õ(n*max(m^{2/3},n)) 的运行时间。在此之前人们已知的最好结果是 Hao & Orlin (1993) 提出的 Õ(nm) 的最小割算法，已保持记录 30 年之久。
Make IIIS Great Again!
