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.