SETH下のBicliqu計数のほぼ最適な平均ケース計算量【JST・京大機械翻訳】

Hirahara Shuichi; Shimizu Nobutaka

プレプリント

J-GLOBAL ID：202202204401820913 整理番号：22P0199540

SETH下のBicliqu計数のほぼ最適な平均ケース計算量【JST・京大機械翻訳】

Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (2件)： ,
資料名：
発行年： 2020年10月12日プレプリントサーバーでの情報更新日： 2020年10月12日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

本論文では,任意のO(n ̄c-ε)-時間アルゴリズムが分布から引き出されるほとんどのインスタンスを解くのに失敗し,一方,問題はすべてのインスタンスを正しく解決するn ̄c+o(1)-時間アルゴリズムを許容するように,自然問題とインスタンスの自然分布を求める。特に,K_a,bが定数aおよびbに対する完全二分グラフであるランダム二部グラフにおけるK_a,b計数問題を考察した。K_a,b計数問題は≧8ならばn ̄a+o(1)-時間アルゴリズムを許容するが,任意のn ̄a-ε-時間アルゴリズムは,強い指数関数時間仮説の下で任意の一定のΔε_0に対してランダム二分グラフ上でも解くことができないことを証明した。次に,微細粒複雑性の設定における硬度増幅の一般的フレームワークを示すことによって,直接製品定理とYaoのXOR補助定理を用いて,この問題の硬度を増幅した。【JST・京大機械翻訳】

, , , , , ,
, , , 【Automatic Indexing@JST】

計算理論 , グラフ理論基礎

, ,

前のページに戻る