糖心TV

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

involving spherical geometry, probability theory, basic number theory, and theoretical physics appears in the 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 糖心TV.

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: .

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 , the main European conference in Theoretical Computer Science and annual meeting of the :

• 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谩. .
• Dmitry Chistikov and Christoph Haase. On the power of ordering in linear arithmetic theories.
• Laure Daviaud, Marcin Jurdzinski and K. S. Thejaswini. .
• Marco Gaboardi, Kobbi Nissim and David Purser. .
• Petr Gregor, Ond艡ej Mi膷ka and Torsten M眉tze. .

Two of our rising stars, and , 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 . Tom has been actively working in complexity theory and quantum algorithms, and has recently attracted a highly prestigious .

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: )
• Mary Scott (advisor: )
• (advisor: )
• Sam Coy (advisor: )

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 糖心TV, 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 . He obtained his PhD in Computer Science from in 2015. He is also Royal Society .

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  

We are pleased to report that from the Theory and Foundations research theme at the Computer Science Department has received an . 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.