Theory and Foundations News - Research - Department of Computer Science

Complexity breakthrough by Dr Shuichi Hirahara

Dr Shuichi Hirahara, a research fellow affiliated with the Theory and Foundations 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).

Fri 03 Feb 2023, 17:36 | Tags: People Highlight Research Theory and Foundations

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:

	Herby Bowen - best overall graduating MSc student in Computer Science
	George Wright - best MSc dissertation in Computer Science entitled "Countering Antimicrobial Resistance with Machine Learning"
	Kartik Jain - best overall graduating MSc student in Data Analytics and best MSc dissertation in Data Analytics entitled "Football analytics: A novel approach to estimate success"

Thu 05 Jan 2023, 15:54 | Tags: People Courses Highlight Research Faculty of Science Teaching

Dr Igor Oliveira awarded an ERC Starting Grant

The European Research Council (ERC) has announced that Dr Igor OliveiraLink opens in a new window is among the winners of its prestigious Starting Grant competition. According to the European Research Council: "The funding is worth in total €636 million and is part of the Horizon Europe programme. It will help excellent younger scientists, who have 2 to 7 years’ experience after their PhDs, to launch their own projects, form their teams and pursue their most promising ideas."

Igor OliveiraLink opens in a new window has been awarded a €1.5M ERC Starting grant for a 5-year project entitled "Synergies Between Complexity and Learning". The project aims to exchange ideas and techniques between Complexity Theory and Learning Theory to accelerate progress in both fields, broaden the arsenal of tools available to attack their open problems, as well as to obtain a deeper understanding of the nature of efficient computation and of its logical aspects.

Two projects in Computer Science and Informatics (PE6 panel) in the United Kingdom were awarded ERC Starting Grants in the 2022 round. The press releaseLink opens in a new window contains more information about the ERC funding programme.

Wed 23 Nov 2022, 07:39 | Tags: Highlight Research Theory and Foundations