論文の概要: Matrix Multiplication: Verifying Strong Uniquely Solvable Puzzles
- arxiv url: http://arxiv.org/abs/2301.00074v1
- Date: Fri, 30 Dec 2022 23:53:51 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-03 15:55:17.148370
- Title: Matrix Multiplication: Verifying Strong Uniquely Solvable Puzzles
- Title（参考訳）: 行列乗算: 強い一様解答可能なノズルの検証
- Authors: Matthew Anderson, Zongliang Ji and Anthony Yang Xu
- Abstract要約: 我々は、一意に解けるパズル(強いUSP)と呼ばれる物体を探索する
我々は、幅$k le 5$の強いUSPの最大サイズに関する厳密な境界を作り、従来の作業よりも大きい小さな幅のパズルを構築し、$k le 12$の強いUSPサイズの上限を改善する。
- 参考スコア（独自算出の注目度）: 0.5801044612920816
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Cohn and Umans proposed a framework for developing fast matrix multiplication
algorithms based on the embedding computation in certain groups algebras. In
subsequent work with Kleinberg and Szegedy, they connected this to the search
for combinatorial objects called strong uniquely solvable puzzles (strong
USPs). We begin a systematic computer-aided search for these objects. We
develop and implement constraint-based algorithms build on reductions to
$\mathrm{SAT}$ and $\mathrm{IP}$ to verify that puzzles are strong USPs, and to
search for large strong USPs. We produce tight bounds on the maximum size of a
strong USP for width $k \le 5$, construct puzzles of small width that are
larger than previous work, and improve the upper bounds on strong USP size for
$k \le 12$. Although our work only deals with puzzles of small-constant width,
the strong USPs we find imply matrix multiplication algorithms that run in
$O(n^\omega)$ time with exponent $\omega \le 2.66$. While our algorithms do not
beat the fastest algorithms, our work provides evidence and, perhaps, a path to
finding families of strong USPs that imply matrix multiplication algorithms
that are more efficient than those currently known.
- Abstract（参考訳）: コーンとウマンスは、ある群代数の埋め込み計算に基づく高速行列乗法アルゴリズムを開発するためのフレームワークを提案した。
その後、kleinberg と szegedy による研究で、彼らはこれを strong uniquely solvable puzzles (strong usps) と呼ばれる組合せ対象の探索と結びつけた。
我々はこれらのオブジェクトの体系的なコンピュータ支援検索を開始する。
我々は,強いUSPであることを確認するために,$\mathrm{SAT}$と$\mathrm{IP}$に還元された制約に基づくアルゴリズムを開発し,実装する。
我々は、幅$k \le 5$の強いUSPの最大サイズに関する厳密な境界を生成し、従来の作業よりも大きい小さな幅のパズルを構築し、$k \le 12$の強いUSPサイズの上限を改善する。
我々の研究は、小さな定数幅のパズルのみを扱うが、強いUSPは、指数$\omega \le 2.66$でO(n^\omega)$時間で動作するような行列乗法アルゴリズムを暗示する。
我々のアルゴリズムは最速のアルゴリズムには勝てないが、我々の研究は証拠を提供し、おそらく、現在知られているものよりも効率的な行列乗算アルゴリズムを暗示する強力な usp の族を見つける道筋を提供する。
関連論文リスト
- Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。
我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。
EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
論文 参考訳（メタデータ） (2023-10-23T18:26:00Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Efficiently-Verifiable Strong Uniquely Solvable Puzzles and Matrix
Multiplication [1.5102346715690758]
我々は,強い一意解答パズル(SUSP)のサブクラスを新たに導入し,解析し,探索する。
これらのパズルは効率よく検証可能であることを示すが、これは一般のSUSPにとって未解決の問題である。
コンピュータサーチにより、従来は小幅で知られていたより大きなSUSPの構築について報告する。
論文 参考訳（メタデータ） (2023-07-12T21:39:13Z) - Fast Matrix Multiplication Without Tears: A Constraint Programming
Approach [8.52818380743467]
$N倍のM$行列と$M倍のP$行列の乗算は、単純な$NMPアプローチが示しているよりも少ない乗算で実現できることが知られている。
これにより、高速行列乗法における制約満足度問題が発生する。
本稿では,高速行列乗算のための非可換アルゴリズムを見つけるための,シンプルながら新しい制約プログラミング手法を提案する。
論文 参考訳（メタデータ） (2023-06-01T19:15:24Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - Choosing the Right Algorithm With Hints From Complexity Theory [16.33500498939925]
我々は,メトロポリスのアルゴリズムが,合理的な問題サイズを考慮に入れた全てのアルゴリズムの中で,明らかに最良のものであることを示す。
このタイプの人工アルゴリズムは、$O(n log n)$ランタイムを持つので、重要度に基づくコンパクト遺伝的アルゴリズム(sig-cGA)は、高い確率で、DLB問題を解くことができる。
論文 参考訳（メタデータ） (2021-09-14T11:12:32Z) - RAMA: A Rapid Multicut Algorithm on GPU [23.281726932718232]
本稿では,マルチカット問題(マグニチュード相関クラスタリング)に対する高並列原始双対アルゴリズムを提案する。
我々のアルゴリズムは、最適距離を推定する原始解と双対下界を生成する。
最大$mathcalO(108)$変数を数秒で、小さな原始双対ギャップで、非常に大規模なベンチマーク問題を解くことができる。
論文 参考訳（メタデータ） (2021-09-04T10:33:59Z) - Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。
提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
論文 参考訳（メタデータ） (2021-03-03T22:42:15Z) - Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU
Networks [48.32532049640782]
ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。
正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
論文 参考訳（メタデータ） (2020-06-22T17:53:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。