이 논문은 리드-솔로몬(Reed-Solomon) 부호의 리스트 디코딩 반경을 존슨 반경 너머로 넓히는 새로운 선형 리스트 크기 상한을 제시한다. 저자는 better.codes 자동연구 프로젝트에서 발견된 기법을 바탕으로, 충분히 큰 표수(characteristic)를 가진 체 위에서 정의된 비율 ρ, 블록 길이 n의 리드-솔로몬 부호가 특정 부분 일치율 α(단, α<√ρ)를 요구할 때 리스트 크기가 C·n으로 선형에 그친다는 것을 증명했다. C와 α는 ρ에만 의존하는 상수다. 이는 임의의 상수 ε에 대해 ρ+ε의 일치율에서 지수를 특정하지 않은 n^c 크기의 리스트를 달성한 최근의 획기적 결과([BCPZZ26], [Jeronimo26])를 보완하는 결과다.
- •리드-솔로몸 부호의 리스트 크기 상한을 존슨 반경 너머 영역에서도 선형(C·n)으로 증명
- •충분히 큰 표수의 체와 부분 일치율 α<√ρ 조건에서 성립하는 결과
- •최근 [BCPZZ26], [Jeronimo26]의 n^c 크기 상한 결과와 상호 보완적인 관계
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
Linear list size bounds for Reed-Solomon beyond the Johnson radius
- 1.better.codes 자동연구 프로젝트 기법을 활용해 Reed-Solomon 부호의 리스트 크기가 존슨 반경을 넘어서도 선형(C·n)임을 증명
- 2.비율 ρ, 블록길이 n인 RS 부호에서 분수 일치도 α<√ρ 조건 하에 리스트 크기 상한이 C·n임을 규명
- 3.최근 획기적 결과([BCPZZ26], [Jeronimo26])가 달성한 n^c 크기·일치도 ρ+ε 결과를 보완하는 별도 기법으로 제시
왜 중요한가?
리스트 복호 이론의 핵심 난제인 존슨 반경 초과 구간의 리스트 크기 한계를 선형으로 좁혀, 오류정정부호 기반 증명시스템(STARK 등) 설계의 효율성 분석에 기여한다.
언급 프로젝트
본문 미리보기
Based on techniques discovered in the better.codes autoresearch project, we show that Reed-Solomon codes of rate $\rho$ and block length $n$ over a field of sufficiently large characteristic, have $C\cdot n$ list size bound when requiring fractional agreement $\alpha$ with a received word; where $C,\alpha$ are constants depending only on $\rho$ and $\alpha0$ with an unspecified constant exponent $c$.
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 11:24AI 초안
