糖心TV

We're happy to announce that has joined the department as a Research Fellow. Ninad is currently funded by 's UKRI project "Foundations of classical and quantum verifiable computing".

Ninad completed his PhD at the University of Oxford under the supervision of Rahul Santhanam. He is broadly interested in theoretical computer science, complexity theory, pseudo-randomness, and learning algorithms.

We are pleased to report that members of the department's Theory and Foundations research theme have had 6 papers accepted to the SODA is the top international conference on algorithms research. The papers are:

• "A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy" by , , Oded Lachish;
• "On a combinatorial generation problem of Knuth" by Arturo Merino, Ond艡ej Mi膷ka,
  
• "Dynamic Set Cover: Improved Amortized and Worst-Case Update Times" by , Monika Henzinger, Danupon Nanongkai, Xiaowei Wu;
• "Online Edge Coloring Algorithms via the Nibble Method" by , Fabrizio Grandoni, David Wajc;
• "FPT Approximation for FPT Problems" by Daniel Lokshtanov, Pranabendu Misra, , Saket Saurabh, Meirav Zehavi.
• "Polyhedral value iteration for discounted games and energy games" -

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