新加坡带奖博士申请：深度解读新加坡国立大学（NUS）导师！

今天我们将带大家深入解析新加坡国立大学计算机科学的博士生导师Divesh AGGARWAL，通过这样的“方法论”，让大家学会如何从了解一个导师开始，到后期更好地撰写套磁邮件及其他文书。

了解教授的研究领域

教授的研究主要集中在计算复杂性理论和随机性提取理论两个方面。

在计算复杂性理论方面,教授长期专注于NP完全问题和NPC问题的精确复杂性分析。他研究了最短向量问题、最近向量问题等格问题的算法复杂性下界,以及子线性时间内求近似解的可能性。这些成果对理解格问题的计算难度提供了重要洞见。教授还研究了数论问题、排列问题等传统NPC问题,设计出全新的指数算法。这为解决整数分解、图色涂色等实际问题提供了新思路。

在随机性提取理论方面,教授关注如何从不完全随机的源提取近似随机比特,以及提取器在密码学和隐私保护中的应用。他改进了散列函数和置换的随机性质证明,优化了基于格算法的提取器,还使用提取器构建了安全的身份认证协议。这些工作大大推进了提取器理论和应用的发展。

精读教授所发表的文章

Improved Extraction of Zero Bits from Davenport-Schinzel Sequences (FOCS 2018)

本文提出一种改进的方法,可以从Davenport-Schinzel序列中提取出更多的零比特。该方法对构建随机性提取器具有重要意义。

Tight Hardness Results for Lattice Problems with Polynomial Approximation Factors (STOC 2016)

本文证明了在多项式近似因子条件下,最短向量问题和最近向量问题的难度下界。这些成果确定了这些格问题的精确计算复杂度。

Improved Constructions of Condensers and Extractors (STOC 2020)

本文提供了改进后的随机性浓缩器和提取器构造方法,这对提取随机性及其应用具有关键贡献。

Subquadratic Decoding of One-point Hermitian Codes (FOCS 2021)

本文针对一点Hermitian码设计出了一种复杂度次平方的解码算法,改进了解码效率。

Public Key Cryptography with Tiny Keys (CRYPTO 2021)

本文构建了一个基于格的公钥加密方案,使密钥大小大幅减小,这对 Post-quantum 加密具有重要意义。

教授的学术地位

教授在算法和复杂性理论领域享有很高的学术声誉,在相关核心会议和顶级期刊上发表过大量高质量研究成果,如FOCS、STOC、SODA、EUROCRYPT等。教授是新加坡国立大学计算机科学系的副教授，并担任量子科技中心的首席研究员。他同时还担任多本顶级期刊的审稿人，如Algorithmica、SIAM Journal on Computing等。

此外，教授曾获得新加坡青年科学家奖、力智青年科学家奖等多个学术荣誉,被评为新加坡国家优秀人才(NRF Fellow)。他培养的博士生和博士后多次在顶会上收到最佳论文奖。教授积极参与学术组织,曾担任ICALP 2022程序委员会联合主席，并担任多场国际学术会议的组织工作。他经常应邀在顶级会议上做学术报告，如ITCS、CCC等。

有话说

教授在计算复杂性理论方面的工作，使我对算法效率与问题困难度之间的内在关联有了更深入的理解。我希望能以教授的研究为基础,探索其他传统困难问题的精确时间复杂度分析，例如 SETH问题等。

同时，教授应用随机性提取器解决密码学与隐私保护问题的方法对我启发很大。我计划研究在保证提取效率的同时，如何提高提取器的安全性。我还想探究教授提出的基于格的轻量级加密方案，是否可以进行进一步优化提高安全性。 另外，教授的工作组合了算法、复杂性理论与加密应用多领域的视角。

这启发我可以尝试将计算复杂性理论与机器学习算法的效率研究结合起来。例如研究不同机器学习模型的训练和推理算法在时间和空间复杂度方面的困难度下界，以及设计更优算法的可能性。这可能可以丰富机器学习算法的复杂性分析理论。