[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

UPDATE: THE REMINDING SEMINAR THAT WAS SENT OUT EARIER WAS THE WRONG DATE:

THEORY SEMINAR

Tuesday, December 2, 2014
Ryerson 251 at 3:00 p.m.
 
Tim Black
University of Chicago – Math Department
Math.uchicago.edu/~timblack
 
Title: “Any Monotone k-Uniform Hypergraph Property is Weakly Evasive”
 
Abstract: The decision-tree complexity of a Boolean function is the number of input bits that must be queried (adaptively) in the worst case to determine the value of the function. A Boolean function in n variables is weakly evasive if its decision-tree complexity is Omega(n).  By k-graphs we mean k-uniform hypergraphs.  A k-graph property on v vertices is a Boolean function on n = \binom{v}{k} variables corresponding to the k-subsets of a v-set that is invariant under the v! permutations of the v-set (isomorphisms of k-graphs).
Rivest and Vuillemin (1976) proved that all non-constant monotone graph properties (k=2) are weakly evasive, confirming a conjecture of Aanderaa and Rosenberg (1973).  Kulkarni, Qiao, and Sun (2013) proved the analogous result for 3-graphs.  We extend these results to k-graphs for every fixed k. From this, we show that monotone Boolean functions invariant under the action of a large primitive group are weakly evasive.
While KQS (2013) employ the powerful topological approach of Kahn, Saks, and Sturtevant (1984) combined with heavy number theory, our argument is elementary and self-contained (modulo some basic group theory).  Inspired by the outline of the KQS approach, we formalize the general framework of "orbit augmentation sequences" of sets with group actions.  We show that a parameter of such sequences, called the "spacing," is a lower bound on the decision-tree complexity for any nontrivial monotone property that is G-invariant for all groups G involved in the orbit augmentation sequence, assuming all those groups are p-groups. We develop operations on such sequences such as composition and direct product which will provide helpful machinery for our applications. We apply this general technique to k-graphs via certain liftings of k-graphs with wreath product action of p-groups.
 
Host: Prof. Alexander Razborov
*Refreshments will be served in Ryerson 255 at 2:30pm*
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20141202/4cbbe10f/attachment.htm