Skip to main content Skip to navigation

FoCS Archive News - Before Sept 20

Grasshopper jumping on a sphere gives new quantum insights

Bloch sphere with grasshopper

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.

Thu 27 Aug 2020, 15:32

Oxford-Warwick Complexity Meetings

Complexity Meetings

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!

Mon 15 Jun 2020, 23:15

Six papers accepted to the 47th ICALP

ICALP 2020

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:

ICALP 2020 papers

Tue 21 Apr 2020, 23:44

Dr Sayan Bhattacharya and Dr Tom Gur promoted to Associate Professor


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.

Tue 21 Apr 2020, 23:26

Dr Alexander Kozachinskiy joins the FoCS group

Dr Alexander Kozachinskiy has joined the department to work as a Research Fellow on the "Solving Parity Games in Theory and Practice" project. He will be working with Dr Marcin Jurdzinski and Prof Ranko Lazic.
Alexander received a PhD degree in Mathematics from the Lomonosov Moscow State University. His thesis is devoted to communication complexity and its connections to other topics in Computational Complexity Theory. Two of Alexander's papers won the Best Student Paper Awards' at the CSR 2016 and CSR 2018 conferences. Before joining the University of Warwick he has also worked as Junior Research Fellow at the Faculty of Computer Science of the Higher School of Economics in Moscow.
Tue 21 Apr 2020, 23:19

Welcome new theory PhD students

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

Sun 27 Oct 2019, 22:05

Dr. Igor Carboni Oliveira joins the FoCS group and the department as a new Assistant Professor

Igor Carboni OliveiraThe 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 

Wed 09 Oct 2019, 12:31

EPSRC funding success for Dr Sayan Bhattacharya

Dr Sayan BhattacharyaWe 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.
Fri 04 Oct 2019, 19:52

Older news