“We do not recommend hailing a taxi on a street because you might get ripped-off with high probability.”
——STOC 2025 官方出行指南
布拉格，古老而迷人的城市，波西米亚公国的中心，神圣罗马帝国的京城，出租车宰客的胜地。或许她真是一位带着爪子的母亲，让你沉醉于她的魅力，又让你感受她的刺痛。
在上财计算机与人工智能学院，需要担心布拉格出行的人是四年级博士生贾荐豪和他的导师NickGravin。春节期间，二人的论文“Approximation Guarantees of Median Mechanism in R^d”被理论计算机顶会Annual ACM Symposium on Theory of Computing (STOC 2025)接收。这是新学院成立以来，也是理论计算机研究中心成立以来，首篇由本校学生参与完成的STOC论文。在祝贺他们的同时，小编对该论文的学生作者贾荐豪同学进行了简短的采访，听他分享他的科研经历和心路历程。
请你简单介绍一下跟Nick老师的论文
的研究内容。
我们研究的是社会选择和设施选址里的一个经典理论问题，叫作中位数算法。论文主要是系统地研究高维空间算法的近似比，得到了一系列和维度无关的常数上界，以及相关的一些推广。
你为什么会选择这个方向，做研究期间
有哪些挑战与突破？
选择设施选址这个方向是一个偶然的机会，来自Nick老师之前的论文的审稿意见。我对这个问题感兴趣的点在于：这是一个非常简洁，清晰的数学问题，即使之前我没有接触过这一领域，场景与算法也都十分容易理解。但与此同时，解决问题本身却非常具备挑战性，需要进行很多尝试与探索。
在这个问题的研究过程中，总体是比较顺利的，主要的挑战是开始的时候我有几次失败的尝试，但在Nick老师的帮助下迎刃而解了。然后一个比较大的挫折是第一次投稿SODA被拒稿。但我逐渐接受这是做研究的常态，然后心理上也开始习惯失败。通过即使的调整，在第一次投稿的基础上迅速加了一些新结果，最后也十分幸运地被STOC接收了。
能否描述一下Nick老师的指导风格？
Nick老师的指导风格比较亲历亲为，在选题方向，问题解决和论文写作上都会提供非常细致的帮助。Nick老师也非常鼓励学生进行沟通，无论是遇到困难还是有一些新想法的时候，积极讨论都会有很大的帮助。
你对正在攻读或准备攻读博士的同学
有什么建议？
首先是保持积极沟通，和导师，同学或者同行多交流，获取反馈，提高研究效率。然后是在面对困难时要能坚持并保持乐观和耐心，博士就读中难免会遇到困难或者瓶颈，要拥有良好的心态积极面对。
作者简介
Nick Gravin，教授
本科：圣彼得堡国立大学
博士x2：圣彼得堡Steklov研究所，新加坡南洋理工大学
博士后：MIT（2016），微软研究院New England（2013-2015）
研究领域：理论计算机，离散数学，概率论，算法博弈论，拍卖机制设计，组合学，凸几何等。
个人主页：ngravin.github.io
贾荐豪， Ph.D candidate
本科：上海财经大学
研究领域：拍卖机制设计，算法博弈论
个人主页：jianhao-jia.github.io
编审 | 王晓
