[Colloquium] Reminder: Wu/Dissertation Defense/April 27, 2018

Thu Apr 26 09:32:26 CDT 2018

This is a reminder about Angela Wu’s defense tomorrow.

	Department of Computer Science/The University of Chicago

				*** Dissertation Defense ***

	Joint PhD program in Mathematics and Computer Science

Candidate:  Angela Wu

Date:  Friday, April 27, 2018

Time:  2:30 pm

Place:  Ryerson 277

Title:  List Decoding Homomorphism Codes

Abstract:
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),    who demonstrated local list-decodability up to minimum distance of homomorphism codes for expanding classes of groups (Boolean, abelian, nilpotent). We further expand the range of groups with this property. 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., the number of codewords within distance (mindist-𝜀) from any received word, when G is 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.

Our main result is efficient local list-decoding for the permutation representations of alternating groups (i.e., when the codomain is a symmetric group Sm) under the restriction that the domain G=An is paired with codomain H=Sm satisfying m < 2^(n-1)/√n.       

The limitations on the codomain in the latter case reflect a gap between uniquely identifying a homomorphism in aHom(An,H) and determining the homomorphism on generators of the whole group. This phenomenon is new and is sure to appear again for other more general classes of domains. Bridging this gap requires solving the Homomorphism Extension Problem (HomExt): given a partial map 𝛾: G ⇀ H (the domain of 𝛾 is a subset of G) decide whether or not there exists a homomorphism 𝜑:  G → H extending 𝛾.

For this reason, we introduce an intermediate algorithmic model we call Certificate List-Decoding that avoids the HomExt bottleneck and works in the alternating versus arbitrary setting.

Our new combinatorial tools allow us to play on the relatively well-understood top layers of the subgroup lattice of the domain, avoiding the dependence on the codomain, a bottleneck in previous work. We also introduce ``mean-list-decoding,'' a relaxation principle for constraints on the domain, that automatically upgrades results such as {abelian→abelian} to {arbitrary→abelian}.

While motivated by bridging the mentioned gap in list-decoding, HomExt is also of independent interest, both as a problem in computational group theory and as a new and natural problem in NP of unsettled complexity status.

We consider the case H=Sm (the symmetric group of degree m), i.e., 𝛾 : G ⇀ H gives a group action by the subgroup generated by the domain of 𝛾. We assume G ≤ Sn is given as a permutation group by a list of generators. We characterize the equivalence classes of extensions in terms of a multidimensional oracle subset-sum problem.  From this we infer that for bounded G the HomExt problem can be solved in polynomial time.

We are most concerned with the case G=An (the alternating group of degree n) for variable n under the assumption that the index of M in G is bounded by poly(n).  We solve this case in polynomial time for all m < 2n-1/√n.  This is the case required for the main list-decoding result.

The Homomorphism Extension results are solo work; the rest are joint with Laszlo Babai and Timothy Black.

Angela’s advisor is Prof. Laszlo Babai

A copy of Angela Wu’s dissertation draft is available at this link: http://math.uchicago.edu/~wu/thesis/thesis.pdf <http://math.uchicago.edu/~wu/thesis/thesis.pdf>

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret Jaffey
Department of Computer Science
Student Affairs Administrator
margaret at cs.uchicago.edu <mailto:margaret at cs.uchicago.edu>
Eckhart 124
773-702-6011
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

_______________________________________________
Colloquium mailing list  -  Colloquium at mailman.cs.uchicago.edu
https://mailman.cs.uchicago.edu/mailman/listinfo/colloquium
_______________________________________________
Phd-students mailing list
Phd-students at mailman.cs.uchicago.edu
https://mailman.cs.uchicago.edu/mailman/listinfo/phd-students
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20180426/64799300/attachment-0001.html>