Best Student Paper Award at ITCS 2022
We are delighted to announce that Peter Kiss, a PhD student in the Theory and Foundations Research Division, has won the Best Student Paper Award at the Innovations in Theoretical Computer Science (ITCS) 2022 conference for his single-author paper on "Deterministic Dynamic Matching in Worst-Case Update Time". Computing a maximum matching in a graph is one of the most fundamental problems in design and analysis of algorithms. The paper makes important progress on this problem in a setting where the input graph is changing over time via a sequence updates, and one wishes to maintain a large matching efficiently in such a dynamic graph. Along the way, the paper develops a general purpose technique for converting any dynamic algorithm with amortised update time into one with worst-case update time, provided the initial algorithm is able to handle a more general form of batch updates.
Members of the High-Performance and Scientific Computing Group (HPSC) at the department of Computer Science has won a best paper award at the 28th IEEE International Conference on High-Performance Computing, Data and Analytics held on the 17th-18th of December. The winning paper titled Predictive Analysis of Large-Scale Coupled CFD Simulations with the CPX Mini-App, develops a novel representative (mini-)application, specifically designed to model coupled execution of multi-physics numerical simulation codes from the CFD domain. The mini-coupler, CPX, is the first of its kind, combining multiple CFD mini-app instances to predict the run-time and scaling behaviour of large scale coupled CFD simulations, on modern multi-core and many-core clusters such as used for production turbomachinery design at Rolls-Royce plc. The work was carried out by PhD candidate, Archie Powell, in collaboration with Kabir Choudry, Arun Prabhakar, and Gihan Mudalige at the Department of CS Warwick, Dario Amirante (University of Surrey), Istvan Reguly (PPCU) and Stephen Jarvis (University of Birmingham).
The work was funded by the EPSRC Prosperity Partnership in Computational Science for Advanced Simulation and Modelling of Engineering Systems (AsiMoV) and Rolls-Royce plc.
This year’s Warwick Postgraduate Colloquium in Computer Science (WPCCS) was held on Monday 14th December and marked the 18th edition of this beloved event. For the first time in its history, WPCCS took place online, on the communication platform MSTeams, to allow everyone to participate safely during the ongoing COVID-19 pandemic.
A cherished occasion to present one’s research, receive valuable feedback, and create connections within the department to develop new ideas, the Colloquium saw the participation of 50 PhD students who gave presentations spread across seven major themes, showcasing the quality and diversity of the research carried out in the Computer Science Department at Warwick. 22 PhD students also submitted longer, more detailed presentations which were made available to participants and attendees on the official WPCCS MSTeam, so to receive constructive in-depth comments.
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.
We are pleased to report that members of the department's Theory and Foundations research theme have had 6 papers 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. The papers are:
- On the central levels problem by Petr Gregor, Ondřej Mička and Torsten Mütze
- Matrices of optimal tree-depth and row-invariant parameterized algorithm for integer programming by Timothy Chan, Jacob Cooper, Martin Koutecký, Dan Král and Kristýna Pekárková
- The Complexity of Verifying Loop-free Programs as Differentially Private by Marco Gaboardi, Kobbi Nissim and David Purser
- Rational subsets of Baumslag-Solitar groups by Michaël Cadilhac, Dmitry Chistikov and Georg Zetzsche
- The Strahler number of a parity game by Laure Daviaud, Marcin Jurdzinski and K. S. Thejaswini
- On the power of ordering in linear arithmetic theories by Dmitry Chistikov and Christoph Haase
The Department of Computer Science and the Mathematics Institute jointly hosted, last Saturday 7th December, the Christmas Meeting for 2019 of the British Society for the History of Mathematics.
Our Departments have a long and strong association with the BSHM which has an established tradition of having its Christmas meeting in the Midlands. With about 50 participants, including some staff and students from both our Departments, there were 8 talks in the day ranging from figurate numbers in the 9th century, Islamic use of sexagesimal calculation for π and sine values in the 15th century, to fascinating details of Victorian data processing and the mathematical semantics of programming languages in more recent times.
There were plenty of interesting questions arising and lively discussions in the refreshment intervals. There was also a presentation of the BSHM Neumann Prize and the Society's AGM.
The day was widely acclaimed as enjoyable and successful. Our thanks are due to both Departments for their sponsorship, to the admin and technical support in Computer Science, and to the local organising work of Steve Russ and Adam Jones. Further information about the BSHM is at https://www.bshm.ac.uk/.
Full list of speakers:
- Helen Ross - Dicuil and triangular numbers
- Steve Russ - Visions in the night: Bolzano's anticipations of continuity
- Jane Wess - From Newton to Newcomen: mathematics and technology 1687-1800
- Troy Astarte - On the difficulty of describing difficult things
- Catalin Iorga - Known and unknown in Al-Kashi's mathematics
- Robin Wilson - Hunting and counting trees: the world of Cayley and Sylvester
- Chris Pritchard - From collecting coins to searching the archives: personal reflections on becoming a historian of mathematics
- Martin Campbell-Kelly - Victorian data processing
We are pleased to report that members of the department's Theory and Foundations research theme have had 7 papers accepted to the 31st Annual ACM-SIAM Symposium on Discrete Algorithms, to be held in Salt Lake City, Utah, USA, January 5-8, 2020. SODA is the premier international conference on algorithms research, and the papers are:
- Parameterized Complexity and Approximability of Directed Odd Cycle Transversal by M. S. Ramanujan, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi
- An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs by Sayan Bhattacharya, Janardhan Kulkarni
- Coarse-Grained Complexity for Dynamic Algorithms by Sayan Bhattacharya, Danupon Nanongkai, Thatchaphol Saranurak
- Combinatorial Generation via Permutation Languages by Elizabeth Hartung, Hung P. Hoang, Torsten Mütze, Aaron Williams
- On the Power of Relaxed Local Decoding Algorithms by Tom Gur, Oded Lachish
- Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity by Alessandro Chiesa, Tom Gur, Igor Shinkar
- Sublinear time approximation of the cost of a metric k-nearest neighbor graph by Artur Czumaj, Christian Sohler