Title: Evasive Boolean Functions (and Evasive Graphs)
Speaker: Patrick Devlin, Rutgers University
Date: Wednesday, October 28, 2015 12:10pm
Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Gollum draws a graph on the ground, and he declares "we thinks of a set of vertices. Does it haves any edgeses?". Bilbo is allowed to ask about vertices one by one via questions of the form "is THIS vertex in your set?", and Gollum answers tricksily (adversarially). Bilbo wins if he manages to answer Gollum's riddle without having to ask about literally every single vertex of the graph.
In the subsequent dialog, Tolkien explores for which graphs Gollum has a winning strategy and calls such graphs "evasive" (otherwise, non-evasive). Following Tolkien's original manuscripts, in this talk we discuss the question of which graphs are evasive, how to test evasiveness, and a striking conjecture that is either extremely interesting or extremely false. We settle the question completely for trees, cycles, and a few other graph families.
Time permitting, we will show connections between this question and the larger framework of more general boolean functions [about which multiple very interesting results have been proven (mostly via neat topological ideas)].
**Note: The speaker is willing to offer anyone one (1) ring of power for a positive proof of the main conjecture or four (4) cakes of lembas bread for a counterexample.