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

Speaker(s)

Paweł Wolff

Affiliation

Uniwersytet Warszawski

Date

Nov. 17, 2005, 12:15 p.m.

Room

room 5850

Seminar

Seminar of Probability Group

---

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.

---