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
Adam Shephard has just joined the department as a Research Fellow and is currently working in the Tissue Image Analytics (TIA) Lab on the ANTICIPATE project funded by Cancer Research UK. He has recently submitted his thesis on the application of deep learning to paediatric MRI at Aston University, under the supervision of Prof. Amanda Wood and Dr. Jan Novak. His role in the ANTICIPATE project will be concerned with the development and application of deep learning techniques to digitized histology slides to aid in the more efficient grading of head and neck tumours, to ultimately provide more accurate patient prognoses.
Dr Theo Damoulas (Department of Computer Science) along with Dr David Armstrong (Department of Physics) and Jevgenij Gamper (Department of Mathematics) have developed probabilistic machine learning algorithms that can separate out real planets from fake ones in the large samples of thousands of candidates found by telescope missions such as NASA’s Kepler and TESS. The results of which have led to fifty new confirmed planets, the first to be not only ranked but also probabilistically validated by machine learning.
The paper "Exoplanet Validation with Machine Learning: 50 new validated Kepler planets" has been accepted to the Monthly Notice of the Royal Astronomical Society, DOI: 10.1093/mnras/staa2498
Work performed by Computer Systems Engineering student Michael Shanta for his 3rd year project, supervised by Dr. Marina Cole and Dr. Siavash Esfahani in the School of Engineering, was written up in a paper that was recently accepted for presentation at the IEEE Sensors 2020 Conference.
For his 3rd year project Michael worked on developing machine learning techniques for an Electronic Nose in order to classify odours based on the sensor responses. The system aims to detect incontinence incidents, allowing alerts to be sent to relevant personnel from an IoT network via a cloud server.
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.
Dr Arshad Jhumka from the department’s Artificial Intelligence research theme has been awarded a grant as PI, under the PETRAS SRF programme, to develop and deploy a trusted edge-based Internet of Things (IoT) network. IoT networks are expected to be deployed as solutions to problems in a wide variety of contexts, from non-critical applications such as smart city monitoring to providing support to emergency services such as critical communications. As IoT devices are resource constrained, execution of resource-hungry applications will be offloaded to edge networks for quick response. Such an infrastructure is open to cyber-attacks and needs to be resilient to attack.
Florin Ciucu has been successful with a 491K EPSRC grant application ‘Practical Analysis of Parallel and Networked Queueing Systems’. The project will run for 4 years and will address some fundamental queueing problems at the core of modern computing and communication systems with parallel or network structures. The technical objective is to develop novel martingale-based models and techniques circumventing the historical Poisson assumption on the systems’ input, which has been convincingly shown to be highly misleading for practical purposes. The proposal was supported by IBM Research, Microsoft Research, and VMware.