[Colloquium] Talk by Gygory Turan, University of Illinois at Chicago on November 17, 2008

[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.