| COMPUTER SCIENCE/DISCRETE MATH, I | |
| Topic: | Influences and Decision Tree Complexity |
| Speaker: | Michael Saks |
| Affiliation: | Rutgers University |
| Date: | Monday, November 1 |
| Time/Room: | 11:15am - 12:15pm/S-101 |
In this talk, I'll present a new inequality which, for an arbitrary boolean function, relates the influence of its variables to decision tree computation of the function. Combining this with another inequality due to Schramm and Steif, we deduce new general lower bounds for randomized decision tree complexity.
This is joint work with Ryan O'Donnell, Rocco Servedio and Oded Schramm.