Members of the FoCS group, 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.

We are excited to announce a new series of meetings on complexity theory jointly organised by Oxford and Warwick.

Meetings take place online and consist of informal talks dedicated to topics of interest in computational complexity theory and related areas. Our goal is for these meetings to serve as a forum for discussion and quick dissemination of results. Note that meetings will not be recorded, and anyone interested in complexity theory is welcome to join.

Information about speakers and talks, as well as information about joining the mailing list, can be found at this link: Oxford-Warwick Complexity Meetings.

We are looking forward to seeing you at the next talk!

Another ICALP is coming, and another good performance of the FoCS group: 6 papers from our group has been accepted to the 47th International Colloquium on Automata, Languages and Programming, the main European conference in Theoretical Computer Science and annual meeting of the European Association for Theoretical Computer Science:

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

Two of our rising stars, Dr Sayan Bhattacharya and Dr Tom Gur, have been promoted to Associate Professor, effective from 1 May 2020. Sayan has made several fundamental contributions in the area of dynamic graph algorithms and has recently attracted an EPSRC New Investigator grant. Tom has been actively working in complexity theory and quantum algorithms, and has recently attracted a highly prestigious UKRI Future Leaders Fellowship.

We welcome four new theory PhD students who have joined the Department this fall (from left to right on the picture):

• Thejaswini K S (advisor: Marcin Jurdzinski)
• Mary Scott (advisor: Graham Cormode)
• Marcel de Sena Dall Angol (advisor: Tom Gur)
• Sam Coy (advisor: Artur Czumaj)

The FoCS group and the Department of Computer Science are welcoming our new Assistant Professor, Dr. Igor Carboni Oliveira, who will be associated with the Division of Theory and Foundations (FoCS) and the Centre for Discrete Mathematics and its Applications (DIMAP).

Before joining Warwick, Igor held postdoctoral positions at the Department of Computer Science at the University of Oxford and at the School of Mathematics at Charles University in Prague, and was a research fellow at UC Berkeley's Simons Institute for the Theory of Computing. He obtained his PhD in Computer Science from Columbia University in 2015. He is also Royal Society University Research Fellow 2019.

His research is primarily focused on the limitations of algorithms and computations, with connections to combinatorics and mathematical logic. For more information about his work and interests, please see his web page at https://www.dcs.warwick.ac.uk/~igorcarb/ 

We are pleased to report that Dr Sayan Bhattacharya from the Theory and Foundations research theme at the Computer Science Department has received an EPSRC New Investigator Award. This will allow him to lead a research project on the theory and applications of dynamic algorithms. The approximately £250K project will aim to develop new techniques to design algorithms for fundamental optimisation problems in a setting where the input data changes over time.

The proposal was ranked top at its funding prioritisation panel, and the reviewers said:

The intended research explorations are of very high quality and will likely make a substantial impact on the research community; and possibly on the industrial sector.