-
Department of CS newsletter
Published: Wednesday, 27 January 2021Weekly newsletter for the Department of CS
Department Newsletter - Contents
[ top ]Wellbeing
[ top ]Events
Atlas Talk 3rd February 2021
Atlas Talk Wednesday 3rd February 2021 at 2pm (online)
Ranko Lazic University of Warwick
Host: Ian Pratt-Hartmann
Join here: https://zoom.us/j/93918368182
The Reachability Problem for Petri Nets is Not Elementary
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. The central algorithmic problem for Petri nets is reachability: whether from the given initial configuration there exists a sequence of valid execution steps that reaches the given final configuration. The complexity of the problem has remained unsettled since the 1960s, and it is one of the most prominent open questions in the theory of verification. Decidability was proved by Mayr in his seminal STOC 1981 work, and the currently best published upper bound is non-primitive recursive Ackermannian of Leroux and Schmitz from LICS 2019. We establish a non-elementary lower bound, i.e. that the reachability problem needs a tower of exponentials of time and space. Until this work, the best lower bound has been exponential space, due to Lipton in 1976. The new lower bound is a major breakthrough for several reasons. Firstly, it shows that the reachability problem is much harder than the coverability (i.e., state reachability) problem, which is also ubiquitous but has been known to be complete for exponential space since the late 1970s. Secondly, it implies that a plethora of problems from formal languages, logic, concurrent systems, process calculi and other areas, that are known to admit reductions from the Petri nets reachability problem, are also not elementary. Thirdly, it makes obsolete the currently best lower bounds for the reachability problems for two key extensions of Petri nets: with branching and with a pushdown stack.
Joint work with Wojciech Czerwinski, Slawomir Lasota, Jerome Leroux and Filip Mazowiecki.
Karon Mee
FREE INNOVATION CLINICS TO GIVE YOUR RESEARCH SOCIAL AND COMMERCIAL IMPACT
The aim of each ‘Innovation Clinic’ is to provide an informal, recurring setting in which participants can engage in an open dialogue about exploring sustainable, alternative, and meaningful ways of achieving impact with their research. These clinics will be hosted by Erol-Valeriu Chioasca, a Senior Project Manager with the Innovation Factory.
The "Innovation Clinics" are held every other Wednesday from 12-2pm, starting 13 January 2021. You can attend easily by Zoom, dropping in any time that suits your schedule. Click here to add these sessions to your calendar. If you have any questions, please get in touch by emailing contact@uominnovationfactory.com. To see a selection of projects that we have helped support, visit www.uominnovationfactory.com
Radina Ivanova
Join us to discuss failure rates in introductory programming courses on Monday 1st February at 2pm
Following on from our discussion of ungrading, this month we’ll be discussing pass/fail rates in introductory programming courses.
As usual, we’ll be meeting on zoom, see sigcse.cs.manchester.ac.uk/join-us for details.
[ top ]PGR News
Remember to Include your PGRs COVID 19 IMPACT Statement!
Acknowledging the impact of COVID-19 on postgraduate research programmes: guidance for PGRs, Supervisors and Examiners on inclusion of a COVID-19 impact statement with theses submitted by PGRs at the University of Manchester.
Files:
- Impact_Statement_FINAL.pdf (570.36 KB)
Simon Harper
PGR Drop in Sessions Start Friday Feb 05th at 14:00-14:30
PGR Drop-in Sessions Start Friday, Feb 05th at 14:00-14:30 and they run every other week. If you're a PGR you'll be getting a calendar invite so look out for it. If you want to attend but aren't a PGR then ping me to get a calendar invite.
- https://zoom.us/j/92517564823
- Passcode: 478443
These are optional sessions and they are there to discuss any issues you may have, both COVID related and non-COVID related. As there will be more than one of the PGR team there you'll be able to have a one to one by moving to a breakout room, and we'll run some set talks around completion, progression and the plain old research and COVID fatigue. And in the space you'll find Bijan and I talking about baking - but this time with a recipe or two!
Vegan Lemon Cake might very well be the first one!
[ top ]BAME News
Emergency Small Grants for Greater Manchester’s ethnic minority communities
Applications close on Friday 26 February 2021 at 4pm.
These grants are funded by Comic Relief and the National Emergency Fund in response to COVID-19. To find out more, and to apply, please visit: Emergency Grants for GM BAME Communities - Small Grants | www.gmcvo.org.uk
“BAME Disabled People Roundtable” held by Disability Rights UK Report
Report: https://www.disabilityrightsuk.org/news/2021/january/disability-rights-uk-release-we-belong-report
They also inform that: The government is now directly consulting with disabled people on the Disability Strategy. An online survey was released on 15 January. If you want to influence the shape of the Strategy, you need to respond by 13 February. We think this time period is far too short and are making representations to government about this. Please do take part in the survey if it is relevant to you and share with your networks: https://disabilityunit.citizenspace.com/cabinet-office/ukdisabilitysurvey/ (scroll all the way to the bottom to start the online survey).
[ top ]Research Funding Opportunities
[ top ]Social Responsibility
