| LDR | | 03090nmm uu200481 4500 |
| 001 | | 000000332805 |
| 005 | | 20240805171623 |
| 008 | | 181129s2018 |||||||||||||||||c||eng d |
| 020 | |
▼a 9780438088016 |
| 035 | |
▼a (MiAaPQ)AAI10809503 |
| 035 | |
▼a (MiAaPQ)uchicago:14344 |
| 040 | |
▼a MiAaPQ
▼c MiAaPQ
▼d 248032 |
| 082 | 0 |
▼a 510 |
| 100 | 1 |
▼a Wuu, Angela. |
| 245 | 10 |
▼a List-decoding Homomorphism Codes. |
| 260 | |
▼a [S.l.] :
▼b The University of Chicago.,
▼c 2018 |
| 260 | 1 |
▼a Ann Arbor :
▼b ProQuest Dissertations & Theses,
▼c 2018 |
| 300 | |
▼a 160 p. |
| 500 | |
▼a Source: Dissertation Abstracts International, Volume: 79-11(E), Section: B. |
| 500 | |
▼a Adviser: Laszlo Babai. |
| 502 | 1 |
▼a Thesis (Ph.D.)--The University of Chicago, 2018. |
| 520 | |
▼a 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 G |
| 520 | |
▼a 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 < |
| 520 | |
▼a 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 |
| 520 | |
▼a 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. |
| 520 | |
▼a 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 |
| 520 | |
▼a 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. |
| 520 | |
▼a We consider the case H=Sm (the symmetric group of degree m), i.e., gamma : G &rarr |
| 520 | |
▼a We are most concerned with the case G=A n (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/"the square root of" n. This |
| 590 | |
▼a School code: 0330. |
| 650 | 4 |
▼a Mathematics. |
| 650 | 4 |
▼a Computer science. |
| 690 | |
▼a 0405 |
| 690 | |
▼a 0984 |
| 710 | 20 |
▼a The University of Chicago.
▼b Mathematics and Computer Science. |
| 773 | 0 |
▼t Dissertation Abstracts International
▼g 79-11B(E). |
| 773 | |
▼t Dissertation Abstract International |
| 790 | |
▼a 0330 |
| 791 | |
▼a Ph.D. |
| 792 | |
▼a 2018 |
| 793 | |
▼a English |
| 856 | 40 |
▼u http://www.riss.kr/pdu/ddodLink.do?id=T14997882
▼n KERIS |
| 980 | |
▼a 201812
▼f 2019 |
| 990 | |
▼a 관리자 |