Two-party computation for functions with string inputs

Prelegent(ci)

Omid Yaghoubi

Afiliacja

University of Warsaw

Język referatu

angielski

Termin

9 lipca 2025 14:15

Pokój

p. 5440

Tytuł w języku polskim

Two-party computation for functions with string inputs

Seminarium

Seminarium „Teoria automatów”

---

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.

---