糖心TV

We are delighted to report that from the Theory and Foundations (FoCS) research theme at the Computer Science Department has received a prestigious EPSRC New Investigator Award. The approximately 拢264K project titled "New frontiers in Parameterizing Away From Triviality鈥� aims to develop novel notions of graph edit distance and investigate their connections to efficient solvability of computationally hard problems.

the proposal identifies research questions that are novel, has the potential to have a broader impact both within and outside academia and it is an exciting project that will break new ground.

We're happy to announce that has joined the department as a Research Fellow. He is currently funded by the project "New approaches to unconditional computational lower bounds", with support from the Royal Society.

Zhenjian Lu will soon defend a PhD thesis in computational complexity at Simon Fraser University under the supervision of Prof. Valentine Kabanets and Prof. Andrei Bulatov.

He is primarily interested in Computational Complexity, Circuit Lower Bounds, Algorithms, Pseudorandomness, Analysis of Boolean Functions, and Meta-Complexity.

has joined the department to work as a Research Fellow on the "Foundations of classical and quantum verifiable computing" project, which is led by .

Sathya completed his PhD in quantum computing at the University of Cambridge under the supervision of Prof. Richard Jozsa. His primary interests are quantum algorithms and computational complexity theory.

Dr Dmitry Chistikov and Professor Mike Paterson, together with physicists Olga Goulko (Boise State University) and Adrian Kent (Cambridge), have published an interdisciplinary paper , solving a probabilistic puzzle on the sphere that has applications to quantum information theory.

Suppose a lawn must cover exactly half the area of a sphere. A grasshopper starts from a random position on the lawn and jumps a fixed distance in a random direction. What shape of lawn maximizes the chance that the grasshopper lands back on the lawn? A natural guess would be that a hemispherical lawn is best. It turns out, however, that this is nearly never the case — there are only a few exceptional jump sizes.

This work involving spherical geometry, probability theory, basic number theory, and theoretical physics appears in the Proceedings of the Royal Society A and shows, apart from concern for the well-being of grasshoppers, that there are previously unknown types of Bell inequalities. The Bell inequality, devised by physicist John Stewart Bell in 1964, demonstrated that no combination of classical theories with Einstein's special relativity is able to explain the predictions (and later actual experimental observations) of quantum theory.

A University press release can be found here.

We are pleased to report that members of the department's Theory and Foundations research theme have had 6 papers accepted to the , the main European conference in Theoretical Computer Science and annual meeting of the . The papers are:

• On the central levels problem by Petr Gregor, Ond艡ej Mi膷ka and Torsten M眉tze
• Matrices of optimal tree-depth and row-invariant parameterized algorithm for integer programming by Timothy Chan, Jacob Cooper, Martin Kouteck媒, Dan Kr谩l and Krist媒na Pek谩rkov谩
• The Complexity of Verifying Loop-free Programs as Differentially Private by Marco Gaboardi, Kobbi Nissim and David Purser
• Rational subsets of Baumslag-Solitar groups by Micha毛l Cadilhac, Dmitry Chistikov and Georg Zetzsche
• The Strahler number of a parity game by Laure Daviaud, Marcin Jurdzinski and K. S. Thejaswini
• On the power of ordering in linear arithmetic theories by Dmitry Chistikov and Christoph Haase

Another piece of excellent news: and have been promoted to Associate Professor, effective from 1 May 2020. Quoting from their recommendations,

Dr鈥疊hattacharya has attracted a very competitive EPSRC New Investigator grant and a high-profile UK-Israel collaborative grant with the Weizmann Institute... . Dr鈥疊hattacharya鈥檚 high standing in the research community is confirmed by his memberships of the programme committees of prestigious conferences, as well as his organisation of international research events. 鈥� Dr鈥疊hattacharya has developed a new 3rd-year core module for Discrete Mathematics students and delivered it for the past three years, as well as now teaching most of a key 1st-year core module for the same degree course.

and

Dr鈥疓ur has attracted a highly prestigious UKRI Future Leaders Fellowship, as well as growing his international leading publications record. He is also growing a successful own research group, having recruited a PhD student and on track to employing several postdocs. 鈥� voluntarily exceeding his workload, Dr鈥疓ur has developed from scratch and currently teaches a popular 4th-year module on quantum computing. Mentioning here only some of his other contributions, Dr鈥疓ur also 鈥� is the organiser of the main departmental research seminar, was an active contributor to the department鈥檚 recent Athena SWAN submission, and has been developing fruitful links with several industrial partners.

it remains to say many congratulations!