Functions computed by Alice and Bob

Prelegent(ci)

Mikołaj Bojańczyk

Afiliacja

University of Warsaw

Język referatu

angielski

Termin

15 października 2025 14:15

Pokój

p. 5440

Tytuł w języku polskim

Functions computed by Alice and Bob

Seminarium

Seminarium „Teoria automatów”

---

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

---