NESTiD Seminar
NESTiD Seminar
NESTiD Seminar Coordinator: Thirupathaiah Vasantam
Here you can find the links to the dedicated webpages for the NESTiD Seminars and videos from previous years: Past NESTiD Seminars
NESTiD Seminar 2026/27
The seminar talks will be streamed online on Teams. Whenever the speaker is physically present in Durham, the presentation will also be in the room MCS3052 at the MCS building (in addition to Teams streaming). Whenever a speaker is not physically present, all people at Durham are invited to watch the Teams seminar in the above room. Below you can find the list of speakers and talks for the year 2026/27. In the schedule of talks below is in UK time.
NOTE: Please refer to the schedule below for any room changes for some selected talks.
Link for 2026-27 Seminar videos: click here
Term 1 of 2026/27:
(online on teams)
| Date and Time | Talk |
|---|---|
| Friday 9 Oct 2026 13:00 – 14:00 (Inaugural talk of the NESTiD seminar series) | Igor Razgon (Durham University, UK) Efficient algorithms for testing equality of Boolean functions Let $f_1$ and $f_2$ be two Boolean functions over the same set of variables and let $C_1$ and $C_2$ be their respective representations. Can we test whether $f_1=f_2$ in time polynomial in $|C_1|$ and $|C_2|$? This problem has natural applications in the area of verification and corresponds to checking equivalence of two circuits. We note that the need of efficient testing in terms of representation sizes rules out the possibility of exhaustive testing on all $2^n$ assignments of the input variables. The efficiency of testing very much depends on the restriction of the representation of the functions. For example the testing is tractable for Ordered Binary Decision Diagrams (OBDDs). It is also known to be coRP for a much more general model called Deterministic Decomposable Negation Normal Form (Deterministic). In our recent work https://arxiv.org/abs/2609.21842 we demonstrated that polynomial time testing is possible for a recently introduced model Tree Decision Diagram (TDD). Very recently we learned of an AI generated proof for an even more general model. In this talk, I will present the equality problem and discuss the corresponding algorithm for OBDDs and for more general models. I will end the talk with a list of open questions. |
| Friday 16 Oct 2026 13:00 – 14:00 | Prof. Ramesh K. Sitaraman (UMass, Amherst, USA) The Story of the Edge: From Content Delivery to Agentic AI Our story begins in the late 1990s, when we created content delivery networks (CDNs) that placed “edge” servers near users in thousands of locations worldwide to cache and serve content. This edge infrastructure helped web pages load quickly and high-quality videos play smoothly. A few years later, the effort to move application logic closer to users, onto edge servers, gave rise to the first edge computing services. Today, the edge delivers most of the world’s content and online services, bringing new challenges. Its central role makes it a critical target for increasingly sophisticated attacks by AI-enabled adversaries. At the same time, the rapid adoption of AI calls for new edge services that can host and serve ML models and AI agents at a global scale, with low latency and at low cost. As the edge becomes an indispensable part of global AI infrastructure, it must also become more sustainable and energy-efficient. Building the edge services of the future is a major scientific endeavor, with unresolved problems that call for close collaboration between academia and industry. |
| Friday 23 Oct 2026 13:00 – 14:00 | Dr. Maxime Flin (Aalto University, Finland) Distributed Graphs Coloring with an Optimal Number of Colors in Sublogarithmic Rounds In the LOCAL model, the graph is seen as a network of computers communicating in synchronous rounds in which each node must outputs its own color, while using as few rounds as possible. In this model, many algorithms are known with polylogarithmic round complexity. Over the last decade, it was shown that, for problems such as Delta+1-coloring, randomization could be used to obtain sublogarithmic round complexity, speeding up exponentially the runtime of deterministic algorithms. Understanding for which problems such speedups can be obtained is a major open question in the field. In a seminal paper, Molloy and Reed [J Comb Theory B, 2014] identified the exact value k_Delta such that (Delta – k)-colorability depends on a local criterion if and only if k <= k_Delta. Bamas and Esperet [STACS, 2019] showed that a similar phenomenon occurs in the LOCAL model: they proved that a (Delta – k)-coloring can be computed in polylogarithmic rounds if and only if k < k_Delta. After explaining the main techniques for obtaining sublogarithmic time algorithms in LOCAL, I will present a recent result [STOC, 2026] showing that (Delta – k)-colorings can be computed in sublogarithmic time. The round complexity is nearly optimal; while Bamas and Esperet showed that using fewer colors requires Omega(n / Delta) rounds. Based on joint work with Magnús M. Halldórsson, Manuel Jakob, and Yannic Maus. |
| Friday 30 Oct 2026 15:00 – 16:00 | Prof. Andrea Richa (ASU, USA) Algorithmic Programmable Matter: From Local Markov Chains to “Dumb” Robots Many programmable matter systems have been developed, including modular and swarm robotics, synthetic biology, DNA tiling, and smart materials. We describe programmable matter as an abstract collection of simple computational elements (particles) with limited memory that each execute distributed, local algorithms to self-organize and solve system-wide problems, such as movement, reconfiguration, and coordination. Self-organizing particle systems (SOPS) have many interesting potential applications like coating objects for monitoring and repair purposes, and forming nano-scale devices for surgery and molecular-scale electronic structures. We describe some of our work on the algorithmic foundations of programmable matter, investigating how macro-scale system behaviors can naturally emerge from local micro-behaviors by individual particles: We utilize tools from statistical physics and Markov chain analysis to translate Markov chains defined at a system level into distributed, local algorithms for SOPS that drive the desired emergent collective behavior for the problems of compression, separation, and foraging, among others. We further establish the notion of algorithmic matter, where we leverage standard binary computation, as well as physical characteristics of the robots and interactions with the environment in order to implement our micro-level algorithms in actual testbeds composed of robots that are not capable of any standard computation. We conclude by addressing full concurrency and asynchrony in SOPS. |
| Tuesday 3 Nov 2026 16.00-17.00 Room: MCS 1022 | Frederick Stock (TU Dresden) |
| Friday 6 Nov 2026 13:00 – 14:00 | Dr. Thorsten Gotte (University of Hamburg, Germany) Title: TBC |
| Friday 13 Nov 2026 13:00 – 14:00 | Johannes Meintrup (THM, University of Applied Sciences Mittelhessen, Germany) Temporal Exploration and Rendezvous via Weisfeiler-Leman Colorings Temporal graphs are graphs whose edge relation changes in discrete time steps. The Temporal Exploration Problem (TEXP) asks for a temporal walk that visits all vertices. We show that every connected temporal graph with n vertices can be explored in O(qn log^3 n) time steps, where q is the number of vertex color classes induced by the 2-dimensional Weisfeiler-Leman (2-WL) coloring. For small q, our bound substantially improves on the known worst-case bound of Theta(n^2) in general connected temporal graphs. A corresponding walk can be constructed in deterministic polynomial time. The upper bound is complemented by lower bounds of Omega(n log n) when q is constant and Omega(qn) when 1 <= q <= n. We also apply our techniques to the Temporal Rendezvous Problem (TRP), in which two agents that do not communicate have to meet on a vertex of the temporal graph. Our exploration algorithm yields that, with only polynomial-time computational power, the agents can meet in O(n log^3 n) time steps, leaving a gap of only log^2 n to the known lower bound. Dogeas, Erlebach, Kammer, Meintrup, and Moses Jr.~[ICALP’24] have shown an O(rn^{1+epsilon}) bound for TEXP, for every fixed epsilon>0, where r is the number of orbits, and an O(n^{1+epsilon}) bound for TRP. Both results require superpolynomial computation time. Our contribution improves upon these results in several ways. First, the dependence on n in the upper bounds on the number of time steps is decreased from n^{1+epsilon} to n log^3 n for both TEXP and TRP. Second, for TEXP, we bound the number of time steps linearly by the parameter q, which is efficiently computable and upper bounded by r. Third, we provide novel deterministic polynomial-time algorithms for both TEXP and TRP. |
| Friday 20 Nov 2026 13:00 – 14:00 | Prof. Kin K. Leung (Imperial College London, UK) Title: TBC |
| Friday 27 Nov 2026 13:00 – 14:00 | Dr. Debleena Thacker (Durham University, UK) Title: TBC |
| Friday 4 Dec 2026 13:00 – 14:00 | Dr. Shreyas Pai (IIT Madras, India) Title: TBC |
| Friday 11 Dec 2026 13:00 – 14:00 | TBA |
Term 2 of 2026/27:
(online on teams)
| Friday 15 Jan 2027 13:00 – 14:00 | Aaron Schild (Google Research) Title: TBC |
| Friday 22 Jan 2027 13:00 – 14:00 | TBA |
| Friday 29 Jan 2027 13:00 – 14:00 | Joschka Roffe (Edinburgh University, UK) |
| Friday 5 Feb 2027 13:00 – 14:00 | TBA |
| Friday 12 Feb 2027 13:00 – 14:00 | TBA |
| Friday 19 Feb 2027 13:00 – 14:00 | TBA |
| Friday 26 Feb 2027 13:00 – 14:00 | TBA |
| Friday 5 Mar 2027 13:00 – 14:00 | TBA |
| Friday 12 Mar 2027 13:00 – 14:00 | TBA |
| Friday 19 Mar 2027 13:00 – 14:00 | TBA |
Term 3 of 2026/27:
(online on teams)
| Friday 30 April 2027 13:00 – 14:00 | TBA |
| Friday 7 May 2027 13:00 – 14:00 | TBA |