Seminars
Seminars from previous years: 2024/25 2023/24 2022/23 2021/22 2020/21 2019/20 2018/19 2017/18 2016/17 2015/16 2014/15 2013/14 2012/13 2011/12 2010/11
ACiD Seminars 2025/26.
| Tues 7th October 2025 13:00 MCS 3052 and online | The Great CSP Swindle! Petar Markovic and Dmitriy Zhuk |
| Tues 14th October 2025 13:00 MCS 3052 and online | ACiD Meeting! |
| Tues 21st October 2025 13:00 MCS 3052 and online | Monotone circuit complexity of matching Bruno Cavalar (Oxford) We show that the perfect matching function on $n$-vertex graphs requires monotone circuits of size $2^{n^{\Omega(1)}}$. This improves on the $n^{\Omega(\log n)}$ lower bound of Razborov (1985). Our proof uses the standard approximation method together with a new sunflower lemma for matchings. |
| Tues 28th October 2025 13:00 MCS 3052 and online | Course Allocation with Credits via Stable Matching David Manlove (Glasgow) In the Course Allocation problem, there are a set of students and a set of courses at a given university. University courses may have different numbers of credits, typically related to different numbers of learning hours, and there may be other constraints such as courses running concurrently. Our goal is to allocate the students to the courses such that the resulting matching is stable, which means that no student and course(s) have an incentive to break away from the matching and become assigned to one another. We study several definitions of stability and for each we give a mixture of polynomial-time algorithms and hardness results for problems involving verifying the stability of a matching, finding a stable matching or determining that none exists, and finding a maximum size stable matching. We also study variants of the problem with master lists of students, and lower quotas on the number of students allocated to a course, establishing additional complexity results in these settings. This work was motivated by the allocation of Honours students to courses within the School of Law at UoG, and I will discuss our experience with this application. This is joint work with Mathijs Barkel, Fraser Paterson and Pepe Rodríguez, and a related paper appeared at SAGT 2025 (see here for the full paper) |
| Tues 4th November 2025 13:00 MCS 3052 and online | |
| Tues 11th November 2025 13:00 MCS 3052 and online | |
| Tues 18th November 2025 13:00 MCS 3052 and online | |
| Tues 25th November 2025 13:00 MCS 3052 and online | |
| Tues 2nd December 2025 13:00 MCS 3052 and online | |
| Tues 9th December 2025 13:00 MCS 3052 and online | |
| Tues 13th January 2026 13:00 MCS 3052 and online | |
| Tues 20th January 2026 13:00 MCS 3052 and online | |
| Tues 27th January 2026 13:00 MCS 3052 and online | |
| Tues 4th February 2026 13:00 MCS 3052 and online | |
| Tues 11th February 2026 13:00 MCS 3052 and online | |
| Tues 18th February 2026 13:00 MCS 3052 and online | |
| Tues 25th February 2026 13:00 MCS 3052 and online | |
| Tues 3rd March 2026 13:00 MCS 3052 and online | |
| Tues 10th March 2026 13:00 MCS 3052 and online | |
| Tues 17th March 2026 13:00 MCS 3052 and online |