The FoCS group Theory Workshop 2021 will take place online on June 28 (Monday).

The workshop will consists of some short talks by our PhD students and postdocs, highlighting their recent research.

For more information about the event please see

https://warwick.ac.uk/fac/sci/dcs/research/focs/activities/theory-workshop-june-2021/Link opens in a new window

We're happy to announce that Ninad Rajgopal has joined the department as a Research Fellow. Ninad is currently funded by Tom Gur'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 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. 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 Marcel Dall'Agnol, Tom Gur, Oded Lachish;
• "On a combinatorial generation problem of Knuth" by Arturo Merino, Ondřej Mička, Torsten Mutze;
  
• "Dynamic Set Cover: Improved Amortized and Worst-Case Update Times" by Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Xiaowei Wu;
• "Online Edge Coloring Algorithms via the Nibble Method" by Sayan Bhattacharya, Fabrizio Grandoni, David Wajc;
• "FPT Approximation for FPT Problems" by Daniel Lokshtanov, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi.
• "Polyhedral value iteration for discounted games and energy games" - Alexander Kozachinskiy

We are delighted to report that Dr Ramanujan SridharanLink opens in a new window from the Theory and Foundations (FoCS)Link opens in a new window 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 Zhenjian LuLink opens in a new window 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.

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

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 Globe-hopping, 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.