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

The contribution The Reachability Problem for Petri Nets is Not Elementary by Wojciech Czerwinski, Slawomir Lasota, Ranko Lazic, Jerome Leroux and Filip Mazowiecki has won a Best Paper Award at the 51st Annual ACM Symposium on the Theory of Computing, to be held on June 23-26, 2019 in Phoenix, AZ.

This work, which was supported by a Leverhulme Research Fellowship, shows that the central verification problem for Petri nets is much harder than has been known since the landmark result of Richard Lipton in 1976. Petri nets, also known as vector addition systems, are a long established model of concurrency with extensive applications in modelling and analysis of hardware, software and database systems, as well as chemical, biological and business processes.