より強力な3SUM指数の下限【JST・京大機械翻訳】

Chung Eldon; Larsen Kasper Green

プレプリント

J-GLOBAL ID：202202221112152858 整理番号：22P0305984

より強力な3SUM指数の下限【JST・京大機械翻訳】

Stronger 3SUM-Indexing Lower Bounds

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

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

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

※このプレプリント論文は学術誌に掲載済みです。なお、学術誌掲載の際には一部内容が変更されている可能性があります。

3SUM-Indexing問題を3SUM問題のデータ構造バージョンとして導入し,低減による静的データ構造に対する強い条件付き下限を証明した。理想的に,3SUM-Indexingの予想硬度は,無条件下限によって置換されるべきである。残念なことに,これは,STOC’20からGolovnevらによって下限される対数的クエリ時間である最強の電流下限を有することを証明から遠い。さらに,それらの下限は,非適応データ構造に対してのみ保持され,それらは適応データ構造に対する下限を明示的に要求した。著者らの主な貢献は,適応データ構造に対する下限である。二次結果として,Golovnev et al.の非適応下界も強化し,それ自身の権利で興味深いことを見出した完全新手法を介して,2ビットプローブ非適応3SUM-Indexingデータ構造に対する強い下限を証明した。【JST・京大機械翻訳】

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

仮説粒子とその他の素粒子

前のページに戻る