文献

J-GLOBAL ID：202002291033122916   整理番号：20A2461390

代数的分岐プログラムのための二次下界【JST・京大機械翻訳】

A quadratic lower bound for algebraic branching programs

著者 (4件)： Chatterjee Prerona (Tata Institute of Fundamental Research, Mumbai, India) ,  Kumar Mrinal (IIT Bombay, India) ,  She Adrian (University of Toronto, Canada) ,  Volk Ben Lee (California Institute of Technology)
資料名： ACM Proceedings  (ACM Proceedings)
号： CCC ’20  ページ： 1-21  発行年： 2020年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 多項式[MATH HERE]を計算する任意の代数分岐プログラム(ABP)が少なくともΩ(n2)頂点を持つことを示した。これは,BaurとStrassen[24,1]の古典的結果に従ったΩ(nlogn)の下限で改善し,Kumar[13]の結果を拡張し,同じ多項式を計算する均一ABPの二次下限を示した。この証明は,行列剛性の文脈において類似のステートメントを暗示する深さ低減の概念に依存し,多項式[MATH HERE]を計算する任意の小さなABPは,構造化された「誤差多項式」ε(x)に対して多項式[MATH HERE]を計算する同じサイズの均一ABPに深く低減できることを示した。証明を完了するために,[13]における下限は十分ロバストであり,ε(x)が適切な構造を持つすべての多項式[MATH HERE]に対して保持し続けることを観測した。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *多項式 ,  剛性 ,  ロバスト性
準シソーラス用語： *下界 , 【Automatic Indexing@JST】

著者キーワード (2件)： 代数的分岐プログラム ,  下界

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (2件)： 分岐 ,  下界