講演抄録/キーワード |
講演名 |
2010-10-15 15:15
Finding a Most-Likely Solution of the Perturbed kLIN Problem ○Osamu Watanabe(Tokyo Inst. of Tech.) COMP2010-37 |
抄録 |
(和) |
The kLIN problem is a problem of solving a system of linear
equations over GF(2) such that each equation consists of k variables.
We consider some random model for generating perturbed kLIN problem
instances and discuss the average-case complexity of finding its
most-likely solution. In particular, we consider the case where k = 3
and give some simple algorithms that solve the problem efficiently
on average. Some theoretical analysis supporting our preliminary
computer experiments is also given. |
(英) |
The kLIN problem is a problem of solving a system of linear
equations over GF(2) such that each equation consists of k variables.
We consider some random model for generating perturbed kLIN problem
instances and discuss the average-case complexity of finding its
most-likely solution. In particular, we consider the case where k = 3
and give some simple algorithms that solve the problem efficiently
on average. Some theoretical analysis supporting our preliminary
computer experiments is also given. |
キーワード |
(和) |
MAX-3LIN / MAX-3XORSAT / 平均時解析 / メッセージ伝播アルゴリズム / 局所探索アルゴリズム / スペクトラル解析手法 / / |
(英) |
MAX-3LIN / MAX-3XORSAT / average-case analysis / message passing algorithm / local search algorithm / spectral method / / |
文献情報 |
信学技報, vol. 110, no. 232, COMP2010-37, pp. 41-46, 2010年10月. |
資料番号 |
COMP2010-37 |
発行日 |
2010-10-08 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2010-37 |