Skip to content

DAN

Seminar

Influences and Boolean functions representations

Servedio, R (Columbia)
Tuesday 29 March 2011, 15:30-16:30

Seminar Room 1, Newton Institute

Abstract

More than twenty years ago the important work of Kahn, Kalai and Linial gave general bounds on the influence of variables in arbitrary Boolean functions over the discrete hypercube. In theoretical computer science, though, often one is interested in particular types of "simple" Boolean functions such as constant-depth circuits, decision trees, low-degree polynomial threshold functions, etc. This additional structure raises the possibility that refined influence bounds can be obtained, and indeed it turns out that this is sometimes the case. This talk will give an overview of several such results and their applications, with an emphasis on currently open questions and directions for future work.

Video

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧