Influence of Intersections of Halfspaces

by
Benjamin Shih

The intersection of halfspaces (linear threshold functions) can express any convex body. In particular, DNF formulae and several other classes of Boolean functions are special cases of intersections of halfspaces over Boolean hypercubes. There is accordingly great interest within computational learning theory with regard to understanding intersections of halfspaces. One possible approach utilizes influence to bound the complexity of learning the intersections of halfspaces. The objective of my research is to explore the influence of intersections of halfspaces over the Boolean hypercube.

Advised by Paul Beame

CSE 403
Wednesday
March 2, 2005
3:30 - 4:20 pm