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