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.

This year’s Warwick Postgraduate Colloquium in Computer Science, WPCCS 2018, took place on Friday 29th June. The colloquium, an annual student-run event, showcased research performed by the postgraduate research (PGR) students in Computer Science, the Centre for Discrete Mathematics and its Applications (DIMAP) and the CDT in Urban Science and Progress.

Continuing a new tradition for the colloquium, this year’s event was held in The Oculus, University of Warwick. In addition to presentations from students in each of the department’s research areas, staff and external speakers offered guest talks. These centred on language design patterns in 2018, the evolution and horizons of Field Programmable Gate Arrays (FPGAs), and WebEXR, an online high dynamic range image viewer.

Florin Ciucu, the director of postgraduate research studies in the Department of Computer Science, said of the event:

WPCCS is an excellent opportunity for our students to widely expose where they currently stand in their research. It’s a fantastic way for them to contribute by sharing their research experiences, ideas and visions with their peers and the wider research community.

WPCCS 2018 showcased over 45 presentations and 25 posters of the latest research in the Department of Computer Science. WPCCS aims to foster an air of collaborative research amongst the department’s PGR students and open many conversations between the department’s postgraduate researchers and others. Thank you to all who attended and participated, we look forward to seeing you again next year.

To find out more about WPCCS 2018 or to provide feedback, please visit https://warwick.ac.uk/wpccs18.