[Colloquium] Reminder: Talk by Gygory Turan Today

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Monday, November 17, 2008
Time: 3:45 p.m.
Place: RY 251

----------------------------------------------------------

Speaker:	Gygory Turan

From:		University of Illinois at Chicago

Title:    Cube Partitions and Decision Trees

Abstract:  It is an often discovered result that every k-term DNF can
have at most 2^k - 1 prime implicants and this bound is sharp. We
complete this result by giving an explicit description of all k-term
DNF with the maximal number of prime implicants: these are DNF that
can be represented as a certain kind of decision tree. The proof uses
a splitting lemma for partitions of the hypercube into neighboring
cubes. We then consider the splittability of general cube partitions,
measuring the influence of variables for the cube partition. We also
discuss the connection between this topic and decompositions of
complete graphs into complete bipartite graphs. Time permitting, we
mention several related open problems. This is joint work with Bob
Sloan and Balazs Szorenyi.

Refreshments will be served prior to the talk in RY 255 at 3:00.