Abstract

In this short and self-contained exposition, we present the random self-reduction for matrix multiplication of Hirahara and Shimizu (STOC23). The reduction builds upon the direct product theorem, which is a standard technique of hardness amplification in average-case complexity theory.

要約

「定数レート」「定数距離」「定数クエリの符号語検査器」の三つの「定数」の性質を併せ持つ符号の存在はSpielmanの博士論文(1996)で提起されて以来30年近く未解決のものであり, そのような符号は効率的なPCPの構成などに応用される. 本稿ではこれを解決したDinurら(STOC2022)による新たな局所検査可能符号(LTC;Locally Testable Code)について簡単に解説する. 彼女らは, ケイリーグラフを2次元複体に自然に拡張した左右ケイリー複体を導入し, それに基づく高次元エクスパンダー符号を提案した. この符号はエクスパンダー符号[Sipser, Spielman, 1996]の自然な拡張である.

要約

ランダムネスを用いると様々な問題に対して効率的なアルゴリズムが設計できることが知られ ている. 例えばグラフ到達性判定, 多項式同一性判定, 行列積判定, 数え上げの近似などは効率的な乱択アルゴリズムが知られている. 一方で, これらの問題を同等の時間で決定的に解けるかどうかはよく分かっていない. このように, 乱択アルゴリズムを決定的なアルゴリズムに変換する手法は脱乱択化と呼ばれ, ランダムネスが本質的に必要かどうかという理論計算機科学の基本的な問いと密接に関連しため盛んに研究されている. このスライドではエクスパンダーグラフの理論計算機科学への応用の一つとして 脱乱択化に焦点を当てて紹介していく.

要約

Lovász local lemmaとは, 発生してほしくない複数のイベントが一つも発生しない確率を下から抑えるのに役立つ手法である. 例えばこれらのイベントが全て独立であればそれらの補事象の確率を全て掛け算すれば良いが, そうではなくある程度の相関がある場合にLovász local lemmaは便利である.

要約

エクスパンダーグラフとは直感的には「辺が満遍なく散らばっている」ようなグラフであり, 理論計算機科学において重要な役割を果たしている. ここではその定義と性質を紹介する.

要約

加法的組合せ論においてよく知られるBogolyubovの補題を用いて行列積などの問題に対してエラー耐性の大きい最悪時から平均時への帰着を与えたAsadi, Golovnev, Gur, Shinkar (STOC22) の結果を解説する.

要約

加法的組合せ論におけるBalog-Szemeredi-Gowersの定理 (BSG定理)とその初等的な証明をself-containedな形で解説する.

要約

Locally Testable CodeとPCP定理の紹介スライド. 身内の勉強会用のスライド.