Colloquia and Seminars

Distributed asynchronous systems often require explicit synchronization to ensure the correct implementation of shared objects. In this talk, I introduce the Delaying the Future approach for reasoning about the ordering of events in distributed executions. Its key idea is that, under certain conditions, events can be postponed without any process noticing the change.

I will show how this technique leads to characterizations of communication requirements in asynchronous message-passing systems and in shared-memory systems under the TSO memory model. The Delaying the Future approach provides a unified way to understand the synchronization required by linearizable implementations of common objects such as registers, stacks, and snapshots.

Protein sequences are abundant in repeating segments, both as exact copies and as approximate segments with mutations. These repeats are important for protein structure and function, motivating decades of algorithmic work on repeat identification. Recent work has shown that protein language models (PLMs) identify repeats, by examining their behavior in masked-token prediction.

To elucidate their internal mechanisms, we investigate how PLMs detect both exact and approximate repeats. We find that the mechanism for approximate repeats functionally subsumes that of exact repeats.

We then characterize this mechanism, revealing two main stages: PLMs first build feature representations using both general positional attention heads and biologically specialized components, such as neurons that encode amino-acid similarity. Then, induction heads attend to aligned tokens across repeated segments, promoting the correct answer.

Our results reveal how PLMs solve this biological task by combining language-based pattern matching with specialized biological knowledge, thereby establishing a basis for studying more complex evolutionary processes in PLMs.

The study of spectral graph determination is a central and fascinating topic in spectral graph theory and algebraic combinatorics. This area investigates the spectral characterization of various classes of graphs, develops methods for constructing and distinguishing cospectral nonisomorphic graphs, and analyzes the conditions under which the spectrum of a graph uniquely determines its structure. In the first part of the seminar, we present both classical results and recent advances in spectral graph determination.

The study of graph symmetries and different notions of transitivity is also of fundamental interest in algebraic graph theory. In the second part of the talk, we examine transitivity properties of Gilbert graphs and their complements, and discuss the main ideas underlying these results.