<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">This is an updated announcement to indicate that Timothy Black is in the Joint PhD program in Mathematics and Computer Science.<div class=""><br class=""><div class=""><br class=""></div><div class=""><span class="Apple-tab-span" style="white-space:pre"> </span> *** Dissertation Defense Announcement ***</div><div class=""><span class="Apple-tab-span" style="white-space:pre"> </span>Joint PhD Program in Mathematics and Computer Science</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">Candidate: Timothy Black</div><div class=""><br class=""></div><div class="">Date: Tuesday, September 3, 2019</div><div class=""><br class=""></div><div class="">Time: 2:30 pm</div><div class=""><br class=""></div><div class="">Place: John Crerar Library (JCL) 298</div><div class=""><br class=""></div><div class="">Title: Group-Theoretic Aspects of Complexity Theory and Coding Theory</div><div class=""><br class=""></div><div class="">Abstract:</div><div class=""><div class="">Group theory has long played a role in complexity theory, and vice versa. We explore two of these connections — to evasiveness, and to local list-decoding.</div><div class=""><br class=""></div><div class="">A boolean function in n variables is weakly evasive if its decision-tree complexity is Ω(n). By k-graphs we mean k-uniform hypergraphs. A k-graph property on v vertices is a boolean function on n = (v choose 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).</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">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 Γ-invariant for all groups Γ 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.</div><div class=""><br class=""></div><div class="">The codewords of the homomorphism code aHom(G, H) are the affine homomorphisms between two finite groups, G and H, generalizing Hadamard codes. Following the work of Goldreich–Levin (1989), Grigorescu et al. (2006), Dinur et al. (2008), and Guo and Sudan (2014), we further expand the range of groups for which local list-decoding is possible up to mindist, the minimum distance of the code. In particular, for the first time, we do not require either G or H to be solvable. Specifically, we demonstrate a poly(1/ε) bound on the list size, i.e., on the number of codewords within distance (mindist - ε) from any received word, when G is either abelian or an alternating group, and H is an arbitrary (finite or infinite) group. We conjecture that a similar bound holds for all finite simple groups as domains; the alternating groups serve as the first test case.</div><div class=""><br class=""></div><div class="">The abelian vs. arbitrary result permits us to adapt previous techniques to obtain efficient local list-decoding for this case. In the alternating vs. arbitrary setting, we obtain a local algorithm that produces partial homomorphisms that uniquely extend to the homomorphisms in the list. We introduce this "semi-algorithmic" model, which we call Certificate List-Decoding, due to the severe technical difficulties in extending partial homomorphisms to full homomorphisms, even when the extension is unique. A homomorphism extender applied to a list of certificates yields the desired list. </div><div class=""><br class=""></div><div class="">The results on list decoding homomorphism codes are joint work with László Babai and Angela Wuu.</div></div><div class=""><br class=""></div><div class="">Timothy Black’s advisor is Prof. László Babai</div><div class=""><br class=""></div><div class="">Login to the Computer Science Department website for details,<br class="">including a draft copy of the dissertation:<br class=""><br class=""><a href="https://newtraell.cs.uchicago.edu/phd/phd_announcements#timblack" class="">https://newtraell.cs.uchicago.edu/phd/phd_announcements#timblack</a></div><div class=""><br class=""></div><div class=""><div class="">
<div dir="auto" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div dir="auto" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div dir="auto" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div class="">=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=</div><div class="">Margaret P. Jaffey</div><div class="">Student Affairs Administrator</div><div class=""> for the PhD program</div><div class="">Department of Computer Science</div><div class="">The University of Chicago</div><div class="">John Crerar Library, Room 350</div><div class="">5730 S. Ellis Ave.</div><div class=""><br class=""></div><div class="">773-702-6011</div><div class="">=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=</div><div class=""><br class=""></div></div></div></div></div></div></div></div></div></div></div><br class="Apple-interchange-newline"><br class="Apple-interchange-newline">
</div>
<br class=""></div></div></body></html>