Absztrakt. A döntési fa talán a legegyszerűbb modell Boole-függvények kiszámítására. A változók értékeinek tesztelésével szertenénk összegyűjteni annyi információt, hogy az f Boole-függvény értékét ismerjük az adott inputon. A kérdések száma a számítás költsége. A modell véletlen változata természetes módon bevezethető. A modell egyszerűsége miatt igen sok tétel igazolható, nagy népszerűségnek örvend.

Gráftulajdonságok véletlen döntési fákkal való kiszámítása egy klasszikus problemakör. Központi sejtése (Karp) mind a mai napig megoldatlan: Nemtriviális, monoton gráftulajdonság véletlen döntesi fa bonyolultsága Omega(v^2) (ahol v a csúcsok szama, azaz a változók n száma \binom{v}{2}). Erről beszélek majd.

A fő cél, hogy ÓDonnell, Saks, Schramm, Servedio: Every decision tree has an influential variable cikkének gondolatmenetébe beletekintsünk.