論文の概要: Efficiently-Verifiable Strong Uniquely Solvable Puzzles and Matrix Multiplication

• arxiv url: http://arxiv.org/abs/2307.06463v1
• Date: Wed, 12 Jul 2023 21:39:13 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-14 16:28:35.078639
• Title: Efficiently-Verifiable Strong Uniquely Solvable Puzzles and Matrix Multiplication
• Title（参考訳）: 効率よく検証可能な強い一様解像と行列乗算
• Authors: Matthew Anderson, Vu Le
• Abstract要約: 我々は,強い一意解答パズル(SUSP)のサブクラスを新たに導入し,解析し,探索する。 これらのパズルは効率よく検証可能であることを示すが、これは一般のSUSPにとって未解決の問題である。 コンピュータサーチにより、従来は小幅で知られていたより大きなSUSPの構築について報告する。
• 参考スコア（独自算出の注目度）: 1.5102346715690758
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We advance the Cohn-Umans framework for developing fast matrix multiplication algorithms. We introduce, analyze, and search for a new subclass of strong uniquely solvable puzzles (SUSP), which we call simplifiable SUSPs. We show that these puzzles are efficiently verifiable, which remains an open question for general SUSPs. We also show that individual simplifiable SUSPs can achieve the same strength of bounds on the matrix multiplication exponent $\omega$ that infinite families of SUSPs can. We report on the construction, by computer search, of larger SUSPs than previously known for small width. This, combined with our tighter analysis, strengthens the upper bound on the matrix multiplication exponent from $2.66$ to $2.505$ obtainable via this computational approach, and nears the results of the handcrafted constructions of Cohn et al.
• Abstract（参考訳）: 我々は高速行列乗算アルゴリズムを開発するための Cohn-Umans フレームワークを前進させる。 我々は,Simplified SUSP(simplified SUSP)と呼ばれる,一意に解けるパズル(SUSP)のサブクラスを新たに導入し,解析し,探索する。 これらのパズルは効率よく検証可能であることを示すが、これは一般のSUSPにとって未解決の問題である。 また、個々の単純化可能なsuspは、無限のsusp族ができる行列乗算指数$\omega$ 上の境界の強さが同じであることも示している。 コンピュータサーチにより、従来は小幅で知られていたより大きなSUSPの構築について報告する。 これは我々のより厳密な分析と相まって、この計算手法によって得られる行列乗法指数の上限を2.66ドルから2.505ドルに強化し、コーンらによる手作り構成の結果に近づいた。

関連論文リスト

• Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
  我々は、スペクトルテール条件数である$kappa_ell$を、システムを表す行列の最小特異値と$ell$2の比として定義する。 結果のいくつかの意味と$kappa_ell$の使用は、Conjugateメソッドのきめ細かい解析を直接改善することを含んでいる。
  論文  参考訳（メタデータ） (2024-05-09T14:56:49Z)
• Efficient Unitary T-designs from Random Sums [0.6640968473398456]
  Unitary $T$-Designsは、量子アルゴリズム、ベンチマーク、トモグラフィ、通信における様々な応用において、量子情報において重要な役割を果たす。 我々は、$tildeO(T2 n2)$量子ゲートを用いたランダム行列理論による$T$-designsの新たな構成を提供する。
  論文  参考訳（メタデータ） (2024-02-14T17:32:30Z)
• KyberMat: Efficient Accelerator for Matrix-Vector Polynomial Multiplication in CRYSTALS-Kyber Scheme via NTT and Polyphase Decomposition [20.592217626952507]
  CRYSTAL-Kyber (Kyber) は、標準化プロセス中に選択された暗号鍵カプセル化機構 (KEM) の1つである。 本稿では,Kyberアーキテクチャのレイテンシとスループットの制約に対する最適化について述べる。
  論文  参考訳（メタデータ） (2023-10-06T22:57:25Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Fast Matrix Multiplication Without Tears: A Constraint Programming Approach [8.52818380743467]
  $N倍のM$行列と$M倍のP$行列の乗算は、単純な$NMPアプローチが示しているよりも少ない乗算で実現できることが知られている。 これにより、高速行列乗法における制約満足度問題が発生する。 本稿では,高速行列乗算のための非可換アルゴリズムを見つけるための,シンプルながら新しい制約プログラミング手法を提案する。
  論文  参考訳（メタデータ） (2023-06-01T19:15:24Z)
• Matrix Multiplication: Verifying Strong Uniquely Solvable Puzzles [0.5801044612920816]
  我々は、一意に解けるパズル(強いUSP)と呼ばれる物体を探索する 我々は、幅$k le 5$の強いUSPの最大サイズに関する厳密な境界を作り、従来の作業よりも大きい小さな幅のパズルを構築し、$k le 12$の強いUSPサイズの上限を改善する。
  論文  参考訳（メタデータ） (2022-12-30T23:53:51Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  共分散行列の明示的な構成を避ける新しい推論手法を提案する。 本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。 いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
  論文  参考訳（メタデータ） (2022-02-25T16:35:26Z)
• Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing [49.73889315176884]
  本稿では、実行時の複雑さをアクション数にサブリニアに持つ最初の証明可能なLeast-Squares Value Iteration(LSVI)アルゴリズムを提示する。 我々は, 近似最大内積探索理論と強化学習の後悔分析との関係を構築する。
  論文  参考訳（メタデータ） (2021-05-18T05:23:53Z)
• 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)
• Multi-View Spectral Clustering with High-Order Optimal Neighborhood Laplacian Matrix [57.11971786407279]
  マルチビュースペクトルクラスタリングは、データ間の固有のクラスタ構造を効果的に明らかにすることができる。 本稿では,高次最適近傍ラプラシア行列を学習するマルチビュースペクトルクラスタリングアルゴリズムを提案する。 提案アルゴリズムは, 1次ベースと高次ベースの両方の線形結合の近傍を探索し, 最適ラプラシア行列を生成する。
  論文  参考訳（メタデータ） (2020-08-31T12:28:40Z)
• SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  SURFは分布を断片的に近似するアルゴリズムである。 実験では最先端のアルゴリズムよりも優れています。
  論文  参考訳（メタデータ） (2020-02-22T01:03:33Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。