상세정보
Export to Refworks부가기능
List-decoding Homomorphism Codes
상세 프로파일
| 자료유형 | 학위논문 |
|---|---|
| 서명/저자사항 | List-decoding Homomorphism Codes. |
| 개인저자 | Wuu, Angela. |
| 단체저자명 | The University of Chicago. Mathematics and Computer Science. |
| 발행사항 | [S.l.]: The University of Chicago., 2018. |
| 발행사항 | Ann Arbor: ProQuest Dissertations & Theses, 2018. |
| 형태사항 | 160 p. |
| 기본자료 저록 | Dissertation Abstracts International 79-11B(E). Dissertation Abstract International |
| ISBN | 9780438088016 |
| 학위논문주기 | Thesis (Ph.D.)--The University of Chicago, 2018. |
| 일반주기 |
Source: Dissertation Abstracts International, Volume: 79-11(E), Section: B.
Adviser: Laszlo Babai. |
| 요약 | 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 |
| 요약 | 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 < |
| 요약 | 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 |
| 요약 | 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 |
| 요약 | 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., gamma : G &rarr |
| 요약 | 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 |
| 일반주제명 | Mathematics. Computer science. |
| 언어 | 영어 |
| 바로가기 | 
: 이 자료의 원문은 한국교육학술정보원에서 제공합니다. |
