Mini-course: Boolean functions, sharp thresholds and percolation models (Florian Schweiger, Université de Genève)

29.11.2023 16:15

Suppose that a group of people needs to decide between two options 0 and 1, but an adversary is trying to influence the election by bribing some of the voters. How should we design our voting system so that it is as resistant to such bribes as possible? This question and related ones have been studied quite intensively in theoretical computer science in the last decades under the name "analysis of Boolean functions". I will give a casual introduction to the most important results in this area.

One consequence of this theory is that a wide class of Boolean functions react very sensitively to small changes in the input, or, more precisely, have "sharp thresholds". Such results are very useful tools when studying percolation models in probability theory, and I will explain one or more examples.

This will be the first part of the mini-course. Part 1 will focus on boolean functions and part 2 on sharp thresholds and percolation models.

Lieu

Bâtiment: Conseil Général 7-9

Room 6-13, Graduate Seminar

entrée libre