Dyskretna analiza harmoniczna i hiperkontrakcja --- zastosowania do badania funkcji boolowskich

Prelegent(ci)

Paweł Wolff

Afiliacja

Uniwersytet Warszawski

Termin

17 listopada 2005 12:15

Pokój

p. 5850

Seminarium

Seminarium Zakładu Rachunku Prawdopodobieństwa

---

Rozważmy funkcję boolowską o $n$ zmiennych, tzn. $f \colon \{-1,1\}^n \to \{-1,1\}$. Wyróżniamy jedną ze zmiennych, powiedzmy $x_i$, a na pozostałych kładziemy losowo (z rozkładem jednostajnym) i niezależnie wartości -1 lub 1. Teraz możliwe są dwie sytuacje: albo wynik funkcji zależy od tego, jaką wartość przypiszemy wyróżnionej zmiennej, albo nie. Prawdopodobieństwo pierwszego zdarzenia będziemy nazywać wpływem zmiennej $x_i$ na wynik funkcji $f$. Pewien krąg zagadnień w teorii złożoności obliczeniowej sprowadza się do pytań na temat pewnych własności funkcji boolowskich, wyrażanych m.in. w terminach wielkości wpływu zmiennych tychże funkcji. W ramach referatu przedstawię wynik z pracy: Kahn, Kalai, Linial, "The influence of variables on boolean functions", kładąc główny nacisk na zaprezentowanie używanych w dowodzie narzędzi --- analizy harmonicznej na kostce dyskretnej i pewnej nierówności hiperkontrakcyjnej, wywodzącej się z klasycznej analizy harmonicznej.

---