英国利物浦大学计算机科学系全奖博士招生 | Prof. Krysta(528)

导师简介

如果你想申请英国利物浦大学 计算机科学系博士，那今天这期文章解析可能对你 有用！今天Mason学长为大详细解析利物浦大学的Prof. Krysta的研究领域和代表文章，同时，我们也推出了新的内容“科研想法&开题立意”，为同学们的科研规划提供一些参考，并且会对如何申请该导师提出实用的建议！方便大家进行套磁！后续我们也将陆续解析其他大学和专业的导师，欢迎大家关注！

作为利物浦大学计算机科学系的杰出教授，导师是当今算法博弈论、机制设计和组合优化领域的重要学者。导师目前担任利物浦大学计算机科学系教授，是该校算法、复杂性理论与优化研究组以及经济学与计算研究组的核心成员。

导师的学术履历颇为丰富，曾获得德国国家研究基金会(DFG)的Emmy Noether奖学金，这一荣誉体现了其在早期学术生涯中的卓越贡献。

导师因其杰出的研究成果荣获第39届国际自动机、语言和程序设计会议的最佳论文奖，这一国际顶级会议的认可进一步确立了其在理论计算机科学领域的学术地位。

研究领域

导师的教学和研究兴趣涵盖了理论计算机科学的多个核心领域。

在近似算法方面，导师专注于设计高效的算法来解决NP-难问题，特别关注贪心算法在组合优化问题中的应用及其近似比的改进。在组合优化领域，导师的研究涉及图论、网络优化、独立集问题等经典问题的算法设计与分析。

在算法博弈论方向，导师深入研究机制设计理论，特别是无货币传递的机制设计、拍卖理论以及在线机制设计等前沿问题。其在计算复杂性方面的研究主要关注各类优化问题的计算难度分析，为理解问题本质复杂性提供了重要的理论基础。

近年来，导师的研究兴趣扩展到了更多跨学科领域，包括区块链技术中的最大可提取价值(MEV)问题、材料科学中的晶体结构预测优化、环境经济学中的网络污染控制等，体现了其敏锐的学术洞察力和对新兴交叉领域的深刻理解。

研究分析

1. Network Pollution Games

(Algorithmica)

这篇发表在国际权威期刊Algorithmica上的论文首次从计算的角度研究了污染控制问题。该研究引入了一个新的网络污染控制模型，其中图的节点代表污染源，边表示污染扩散的影响。研究建立了一个数学框架，将污染控制的组合任务编码为整数规划问题，使政府监管机构能够在局部和全局污染限制下最大化社会福利。

2. The Power of Verification for Greedy Mechanism Design

(Journal of Artificial Intelligence Research)

这篇发表在顶级人工智能期刊JAIR上的论文深入研究了贪心机制设计的理论基础。研究使用优先级算法和弱验证、强验证的框架，在这个框架中，出价者不被允许在其获胜集合或该集合的任何子集上出价过高。

该论文提供了弱验证能力的完整刻画，证明了弱验证对于任何贪心固定优先级算法变得诚实是充分且必要的，无论是否使用货币。更重要的是，研究表明强验证对于在有限出价域中获得基于已知贪心算法的子模组合拍卖问题的2-近似诚实机制是充分且必要的。该研究的证明基于对声明图强连通分量的有趣结构分析。

3 MEV Sharing with Dynamic Extraction Rates

(2024)

这是导师在区块链领域的最新重要贡献，发表于2024年的去中心化金融与安全研讨会。该研究提出将MEV提取率作为协议设计空间的一部分，目标是利用这个参数在需要补偿的区块生产者和需要被鼓励进行交易的用户之间维持健康的平衡。研究遵循EIP-1559引入的方法，设计了一个类似的机制来动态更新MEV提取率，目标是将其稳定在目标值。研究分析了这种动态机制的性质，表明虽然对于某些参数可以保证收敛到目标值，但在其他情况下可能出现不稳定甚至混沌现象。

4. Power of Posted-price Mechanisms for Prophet Inequalities

(SODA, 2024)

这篇在算法领域顶级会议SODA 2024发表的论文研究了在组合可行性约束下贝叶斯在线优化问题的发布价格机制能力。当目标是最大化社会福利时，该问题在Prophet不等式文献中被广泛研究。研究表明任何Prophet不等式都有使用发布价格机制的实现，从而解决了Dütting等人提出的开放问题。该研究给出了一个算法，能够将任何贝叶斯在线优化算法以黑盒方式转换为具有相同或更高期望社会福利的发布价格算法，并保持分配结果的分布。作为直接结果，研究获得了最大权重匹配的改进的基于定价的Prophet不等式，解决了Ezra等人提出的开放问题。

5. Optimality guarantees for crystal structure prediction

(Nature, 2023)

这是导师在跨学科研究方面的重大突破，发表在顶级期刊Nature上。该研究表明，晶体材料的结构可以通过结合组合优化和连续优化的算法以能量保证的方式进行预测。

研究将在晶格上找到所有原子的最低能量周期分配的组合任务编码为整数规划的数学优化问题，使用成熟的算法能够保证识别全局最优解。该研究建立了晶体结构预测与算法理论之间的联系，为观察到的或预测的材料提供了绝对的能量状态。这种表述为启发式或数据驱动的结构预测方法提供了基准真值，并且特别适合量子退火器，为克服原子配置的组合爆炸开辟了道路。

6. Ultimate Greedy Approximation of Independent Sets in Subcubic Graphs

(Algorithmica, 2024)

这篇发表在Algorithmica期刊上的论文研究了子三次图中独立集问题的贪心近似算法。该研究通过深入的理论分析，改进了经典贪心算法在特殊图类上的近似比，为组合优化中的基础问题提供了新的洞察。研究不仅具有重要的理论价值，也为实际应用中的图优化问题提供了有效的算法工具。

项目分析

1. Leverhulme Research Centre for Functional Materials Design

(2016-2027)

这是导师参与的重要跨学科研究项目，由Leverhulme Trust资助，项目周期长达11年。该项目旨在开发新的功能材料设计方法，结合计算机科学的算法优化技术与材料科学的实验研究。导师在项目中主要负责算法设计和优化理论方面的工作，特别是在晶体结构预测的计算复杂性分析和高效算法设计方面发挥了关键作用。该项目的成功体现在Nature论文的发表，证明了算法理论在材料科学中的重要应用价值。

2. Efficient Algorithms for Mechanism Design Without Monetary Transfer

这个由英国工程与物理科学研究委员会(EPSRC)资助的项目专注于无货币传递的机制设计算法研究。该项目的核心目标是设计不依赖于货币激励的高效机制，这在许多实际应用场景中具有重要意义，如资源分配、公共决策等。导师在此项目中深入研究了验证机制的理论基础，发展了贪心机制设计的新理论框架，相关成果发表在JAIR等顶级期刊上。

3. Efficient Decentralised Approaches in Algorithmic Game Theory

这个EPSRC资助的项目探索了算法博弈论中的去中心化方法。项目研究了在分布式环境下如何设计高效的博弈理论机制，特别关注网络环境中的策略交互和均衡计算。该项目为后续在区块链和分布式系统中的研究奠定了重要基础，体现了导师在前瞻性研究方向上的敏锐洞察力。

研究想法

1. 区块链机制设计方向

• 动态MEV分配的多链博弈理论研究：随着多链生态系统的发展，不同区块链之间的MEV竞争和合作成为新的研究热点。可以研究跨链MEV分配机制，设计考虑链间交互的动态定价策略，分析多链环境下的纳什均衡和社会最优解。
• 基于零知识证明的隐私保护MEV机制：结合最新的零知识证明技术，设计在保护交易隐私的同时仍能实现公平MEV分配的机制。研究在信息不对称条件下的机制设计问题，探索隐私、效率和公平性之间的权衡。
• 去中心化自治组织(DAO)中的投票机制优化：研究在DAO治理中如何设计抗操控的投票机制，考虑代币持有分布、投票权重、时间激励等因素，设计既保证民主性又提高效率的决策机制。

2. 组合优化与近似算法方向

• 量子启发的组合优化算法：借鉴量子计算的思想，设计新的经典算法来解决NP-难的组合优化问题。研究量子退火算法在经典计算机上的模拟，探索其在图着色、TSP等问题上的应用潜力。
• 机器学习增强的近似算法：结合深度学习技术，设计自适应的近似算法。研究如何利用历史数据和模式识别来改进传统近似算法的性能，特别是在动态和在线优化场景中。
• 多目标组合优化的帕累托前沿快速计算：研究在多个冲突目标下的组合优化问题，设计高效算法来逼近帕累托最优解集。在保证解质量的同时大幅减少计算时间。

3. 跨学科应用方向

• AI驱动的材料设计优化框架：扩展晶体结构预测的工作，结合机器学习和传统优化算法，设计能够预测具有特定性质材料的智能系统。研究如何在巨大的化学空间中高效搜索目标材料。
• 可持续能源系统的博弈论优化：研究分布式能源网络中的策略交互，设计激励可再生能源参与的市场机制。考虑储能、电网稳定性、碳排放等多个约束条件。
• 生物信息学中的网络优化：将网络博弈的思想应用到蛋白质网络、基因调控网络等生物系统中，研究生物网络的稳定性和功能优化问题。

申请建议

1. 学术背景强化

• 理论基础夯实：深入学习算法设计与分析、计算复杂性理论、博弈论基础等核心课程。特别要掌握近似算法、在线算法、机制设计等专业知识。建议系统学习Vazirani的《Approximation Algorithms》、Nisan等的《Algorithmic Game Theory》等经典教材。
• 数学能力提升：加强概率论、图论、线性代数、优化理论等数学基础。导师的研究经常涉及复杂的数学证明和分析，扎实的数学功底是必需的。特别要熟练掌握概率分析、线性规划、整数规划等工具。
• 编程技能培养：虽然导师的研究偏重理论，但也需要具备实现和验证算法的能力。建议掌握Python、C++等编程语言，熟悉常用的优化求解器如Gurobi、CPLEX等。

2. 研究经验积累

• 相关研究项目参与：积极参与算法设计、机制设计相关的研究项目。可以从简单的问题开始，如实现经典的近似算法，分析其性能，逐步积累研究经验。
• 论文阅读与复现：深入阅读导师的代表性论文，理解其研究思路和技术方法。尝试复现论文中的主要结果，这不仅能加深理解，也能培养独立研究能力。
• 跨学科知识拓展：关注区块链、材料科学、环境经济学等导师涉足的跨学科领域。了解这些领域的基本概念和挑战，为将来的研究合作做好准备。

3. 研究能力展示

• 独立研究成果：尝试在导师的研究方向上产出一些初步成果，如改进现有算法、提出新的问题变体等。即使是小的贡献也能体现研究潜力。
• 学术交流能力：参加相关的学术会议和研讨会，了解领域前沿动态。积极参与学术讨论，培养学术交流能力。可以考虑参加ICALP、SODA、EC等顶级会议。

4. 申请策略制定

• 研究计划精准定位：基于导师的最新研究兴趣，制定具体可行的研究计划。避免过于宽泛或脱离导师研究方向的计划。建议选择1-2个具体问题深入研究，展示深度思考能力。
• 个人陈述差异化：突出自己在相关领域的独特优势和研究潜力。避免泛泛而谈，要有具体的例子和成果支撑。特别强调自己的数学背景、编程能力和跨学科视野。
• 推荐信策略性安排：选择熟悉自己研究能力的导师撰写推荐信，最好是在算法、优化或博弈论领域有声誉的学者。确保推荐信能够具体描述自己的研究潜力和学术品质。

博士背景

Aurelia ，美国TOP10院校计算机科学与认知科学双博士生，研究聚焦算法博弈论不确定性及其在人工智能中的应用。她的跨学科研究融合了计算机科学、语言学和心理学知识，在国际顶级期刊《Journal of Artificial Intelligence Research》和《Cognitive Science》上发表多篇论文。Aurelia 荣获ACM SIGAI博士论文奖，擅长相关方向的PhD申请指导。