[日時] 2023年4月21日(金) 12:20--13:20
[場所] 東京大学 本郷キャンパス 工14号館 534室
[講演者] 清水 伸高 (東京工業大学)
[題目] Hardness Self-Amplification: Simplified, Optimized, and Unified
[概要]
平均時計算量では問題と入力分布の組を分布問題と呼び, その分布に従って生成された入力に対してアルゴリズムが間違える確率(すなわち困難な入力の割合)を議論する. 任意の効率的なアルゴリズムに対してその確率が小さくなる問題を弱困難, 大きくなる問題を強困難であるという. 弱困難な問題を強困難な問題に変換する手法を困難性増幅と呼び, 脱乱択化や暗号学的プリミティブの構成などの文脈で盛んに研究されている. これらの文脈では(できるだけ弱い仮定の下で)強困難な問題を陽に構成することを目標としており, そのため困難性増幅によって得られた強困難な問題は変換前の弱困難な問題とは全く異なり人工的な問題となってしまう.近年, 困難性増幅であって変換前後の分布問題が同じである困難性自己増幅(hardness self-amplification)の研究がされている. [Asadi, Golovnev, Gur, Shinkar, STOC2022]は加法的組合せ論の定理(Bogolyubov-Ruzsaの定理)に基づいて行列積に対するランダム自己帰着を与え, [Hirahara, Shimizu, FOCS2022]は平均時計算量の手法(脱乱択化されたXOR補題)に基づいてグラフの三角形偶奇数え上げ問題に対して困難性自己増幅を与えた. 困難性自己増幅の手法は従来の困難性増幅の手法とは違い変換前後の問題が同じであるため自然な問題に対しても適用できるという利点がある.本セミナーではこれらの全く異なる手法に基づく結果を統一された枠組みに基づく別証明を与えた. この別証明は元の証明より驚くほど単純かつパラメータを大きく改善する. さらに, この枠組みに基づいて埋め込みクリーク問題に対して初の困難性自己増幅を与えた. この枠組みは1クエリ帰着が誘導する二部グラフを考え, これがエクスパンダー性を持つならばその帰着は困難性を増幅するというものである. 本セミナーではこの枠組みに基づいた埋め込みクリーク問題に対する困難性自己帰着の手法を解説する. 本研究はNIIの平原秀一氏との共同論文[Hirahara, Shimizu, STOC2023]に基づくものである.
[abstract]
Strong (resp. weak) average-case hardness refers to the properties of a computational problem in which a large (resp. small) fraction of instances are hard to solve. We develop a general framework for proving hardness self-amplification, that is, the equivalence between strong and weak average-case hardness. Using this framework, we prove hardness self-amplification for popular problems, such as matrix multiplication, online matrix-vector multiplication, triangle counting of Erd\H{o}s--R\'enyi random graphs, and the planted clique problem. As a corollary, we obtain the first search-to-decision reduction for the planted clique problem in a high-error regime. Our framework simplifies, improves, and unifies the previous hardness self-amplification results.Our approach uses a one-query upward self-reduction, that is, a reduction that maps a small instance to a large instance. We demonstrate that this reduction yields hardness self-amplification if the bipartite graph, whose left and right vertices correspond to small and large instances, respectively, has an expansion property. Our key technical contribution is to show the expansion property of the bipartite graph naturally constructed from the planted clique problem by using the coupling method of Markov chains.This is a joint work with Shuichi Hirahara (NII) and will appear in STOC2023.
Paper link:
https://eccc.weizmann.ac.il/report/2023/026/