Functions computed by Alice and Bob

Speaker(s)

Mikołaj Bojańczyk

Affiliation

University of Warsaw

Language of the talk

English

Date

Oct. 15, 2025, 2:15 p.m.

Room

room 5440

Title in Polish

Functions computed by Alice and Bob

Seminar

Seminar Automata Theory

---

I will return to a topic discussed by Omid in the last semester, namely functions that can be computed in a distributed protocol by two parties, called Alice and Bob. I will be mainly interested in string-to-Boolean, string-to-string functions and string-to-number functions. There is evidence – and in some cases proofs – that this model corresponds to previously known automata models, and thus characterises them in a machine independent way. It seems we have stumbled upon some new notion of “regularity” for functions, which we are currently investigating.

Joint work with Aliaume Lopez, Rafał Stefański and Omid Yaghoubi

---

I will return to a topic discussed by Omid in the last semester, namely functions that can be computed in a distributed protocol by two parties, called Alice and Bob. I will be mainly interested in string-to-Boolean, string-to-string functions and string-to-number functions. There is evidence – and in some cases proofs – that this model corresponds to previously known automata models, and thus characterises them in a machine independent way. It seems we have stumbled upon some new notion of “regularity” for functions, which we are currently investigating.


Joint work with Aliaume Lopez, Rafał Stefański and Omid Yaghoubi

---