本周六（9月25日）下午1:00，学堂112，将举行本学期第一次seminar。本次有两位七字班的学长来分享，时长约为一到两小时。
来自MIT七字班的毛啸同学，将会分享自己关于Tree Edit distance、刚刚被FOCS 2021接收的single author paper。
来自计算机系七字班的刘潇同学，将会分享自然语言处理中预训练模型的前生今世与未来。
毛啸：Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance
The (unweighted) tree edit distance problem for n node trees asks to compute a measure of dissimilarity between two rooted trees with node labels. The current best algorithm from more than a decade ago runs in O(n^3) time. This algorithm would also work for the weighted tree edit distance problem, which cannot be solved in truly sub-cubic time under the APSP conjecture. In this talk, we break the cubic barrier by showing an O(n^{2.9546}) time algorithm for the unweighted tree edit distance problem by reducing it to max-plus product of bounded-difference matrices, which can be solved in truly sub-cubic time.
刘潇：Pretrained Language Models: Past, Present and Future
Natural Language Processing (NLP) is one of the most important application fields of machine learning. As the emergency of giant pretrained language model GPT-3, NLP has come to its turning point as AlexNet for computer vision. In this talk, we will briefly review the history of pretrained language models, and focus on the current breakthroughs and challenges brought by BERT and GPT-3. Finally, we will discuss several fundmental problems of NLP and how researchers now think of them.
Make IIIS Great Again!
