Two-party computation for functions with string inputs

Speaker(s)

Omid Yaghoubi

Affiliation

University of Warsaw

Language of the talk

English

Date

July 9, 2025, 2:15 p.m.

Room

room 5440

Title in Polish

Two-party computation for functions with string inputs

Seminar

Seminar Automata Theory

---

I will describe a model of computation, which describes functions that input strings, and output elements from some domain, such as the Booleans, or strings, or a field. The idea is that there are two parties, Alice and Bob, who cooperate to compute the output of the function. For a given input string, an adversary chooses a partition $w=w_1w_2$, and sends the words $w_1$ and $w_2$ to Alice and Bob, respectively. Alice and Bob then exchange a constant number of messages, using some operations in the output domain, in a way that results in the output of the function. We will show that for various output domains, the model coincides with standard notions. In particular, for Boolean outputs, it gives regular languages, and for outputs in a field, it gives weighted automata.

Joint work with Aliaume Lopez, Rafał Stefański, and Mikołaj Bojańczyk.

---