Departmental news

We are delighted to report that Dr Ramanujan Sridharan (PI) from the Theory and Foundations (FoCS) research theme at the Department of Computer Science and Professor Graham Cormode (Co-I, affiliated with FoCS) have been awarded an EPSRC Standard Research Grant, "New Horizons in Multivariate Preprocessing (MULTIPROCESS)".

This 4-year £540K project aims to advance the theory of preprocessing by designing novel multivariate preprocessing algorithms and extending their scope to high-impact big data paradigms such as streaming algorithms.

The Mathematical Association of America has presented Mike Paterson with a 2021 Paul Halmos - Lester Ford Award for an article of "expository excellence published in The American Mathematical Monthly". There were several unusual aspects to this paper: the title, "A head-ache causing problem"; the authors, "Conway, J.H., Paterson, M.S., and Moscow, U.S.S.R"; the sole reference in the paper is to itself; the main result is first disproved and then proved; and the acknowledgments make clear that Conway wrote the paper. Paterson previously received this award in 2010 (then the Lester Ford Award) for his "Overhang" article. More information can be found here.

In further good news, Dr Tanaya Guha and Dr Ramanujan Sridharan have been promoted to Associate Professor, effective from 1 July 2021 and 2 October 2021 (respectively). Many congratulations to them, whose recommendations in particular state:

[Dr Guha has] grown her research group to five PhD students currently, and attracted a portfolio of research grants in her career, including recently a substantial award from Ford. ... In engagement, Dr Guha has been raising the visibility of Warwick in her national and international research communities through her invited talks, leadership in the Association for the Advancement of Affective Computing, programme committee memberships, and conference organisation activities. She has also contributed substantially to the Sutton Trust summer school, a key outreach programme.

and

Dr Sridharan’s high standing in the research community is confirmed by his invited talks at international meetings and leading universities, memberships of the programme committees of prestigious conferences, and his organisation of international research events. ... In teaching, Dr Sridharan has successfully led (jointly and individually) two undergraduate modules. The feedback from students has been generally positive, with many appreciative of Dr Sridharan’s innovative and energetic delivery.

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/

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 Sridharan 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 Zhenjian Lu 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.