Artificial Intelligence News
Complexity breakthrough by Dr Shuichi Hirahara
Dr Shuichi Hirahara, a research fellow affiliated with the Theory and FoundationsLink opens in a new window group and an Associate Professor at the National Institute of Informatics in Tokyo, has made a significant advance towards our understanding of the limits and possibilities of efficient computations. In his recent paper "NP-Hardness of Learning Programs and Partial MCSP", published at the 63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS 2022), Dr Hirahara established the NP-hardness of learning efficient programs and of estimating the circuit complexity of an explicitly given partial Boolean function. The main result of the paper addresses a question that dates back to the pioneering work of Stephen Cook and Leonid Levin on the theory of NP-completeness from the 1970s.
The new result has been presented at several institutions, including UT Austin, Columbia University, Warwick (Online Complexity Seminar), MIT, and the Simons Institute for the Theory of Computing at UC Berkeley. The latter is running a semester-long program on "Meta-Complexity" that is closely related to Hirahara's recent contributions.
You can read more about it at the popular Computational Complexity Blog, where the discovery has been named "Complexity Result of the Year" (see also Gödel’s Lost Letter and P=NP).
DIMAP Theory Day 2022
On December 12, 2022, we held the DIMAP Theory Day 2022. This event highlighted recent, exciting advances in the field of Algorithms and Complexity and provided means to facilitate interactions within the algorithms research community in the UK. The event was supported by the Centre for Discrete Mathematics and its Applications (DIMAP) and UKRI. We plan to hold further events in this series on a regular basis.
See more details at the DIMAP Theory Day 2022 page
Outstanding MSc students
The department would like to congratulate our 2021-2022 MSc students on their end-of-year results. Additional congratulations go to the following outstanding students, who have been awarded academic prizes:
 |
|
 |
|
 |
|