論文の概要: Improving Algorithmic Efficiency using Cryptography
- arxiv url: http://arxiv.org/abs/2502.13065v2
- Date: Tue, 22 Apr 2025 17:51:42 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-23 19:51:40.230929
- Title: Improving Algorithmic Efficiency using Cryptography
- Title（参考訳）: 暗号を用いたアルゴリズム効率の向上
- Authors: Vinod Vaikuntanathan, Or Zamir,
- Abstract要約: 計算問題を解く際の時間的複雑さを改善するために暗号を用いる方法を示す。
標準的な暗号仮定の下では、既存のアルゴリズムよりも決定的に高速なアルゴリズムを設計できることを示す。
- 参考スコア（独自算出の注目度）: 11.496343300483904
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Cryptographic primitives have been used for various non-cryptographic objectives, such as eliminating or reducing randomness and interaction. We show how to use cryptography to improve the time complexity of solving computational problems. Specifically, we show that under standard cryptographic assumptions, we can design algorithms that are asymptotically faster than existing ones while maintaining correctness. As a concrete demonstration, we construct a distribution of trapdoored matrices with the following properties: (a) computationally bounded adversaries cannot distinguish a random matrix from one drawn from this distribution (under computational hardness assumptions), and (b) given a trapdoor, we can multiply such an $n \times n$ matrix with any vector in near-linear (in $n$) time. We provide constructions both over finite fields and over the reals. This enables a broad speedup technique: any algorithm relying on a random matrix -- such as those that use various notions of dimensionality reduction -- can replace it with a matrix from our distribution, achieving computational speedups while preserving correctness. Using these trapdoored matrices, we present the first uniform reduction from worst-case to approximate and average-case matrix multiplication with optimal parameters (improving on Hirahara--Shimizu STOC 2025, albeit under computational assumptions), the first worst-case to average-case reductions for matrix inversion, solving a linear system, and computing a determinant, as well as a speedup of inference time in classification models.
- Abstract（参考訳）: 暗号プリミティブは、ランダム性や相互作用の排除や削減など、様々な非暗号化目的に使用されている。
計算問題を解く際の時間的複雑さを改善するために暗号を用いる方法を示す。
具体的には、標準的な暗号仮定の下では、正確性を保ちながら、既存のアルゴリズムよりも漸近的に高速なアルゴリズムを設計できることを示す。
具体的な実演として、以下の性質を持つトラップドア行列の分布を構築する。
(a)計算的に有界な敵は、この分布から引き出された行列(計算硬度仮定の下で)とランダム行列を区別することができず、
b) トラップドアが与えられた場合、そのような$n \times n$行列と任意のベクトルを($n$で)ほぼ線形に乗算することができる。
有限体上の構成と実数上の構成を提供する。
例えば、次元の減少という様々な概念を使うアルゴリズムは、我々の分布から行列に置き換えることができ、正確性を保ちながら計算速度を上げることができる。
これらのトラップドア行列を用いて、最適パラメータによる最悪の行列乗算と平均行列乗算(平原-清水STOC 2025の改良)、行列の逆転、線形システムの解法、行列の計算における最初の最悪の行列減算、および分類モデルにおける推論時間の高速化を示す。
関連論文リスト
- Tensor networks based quantum optimization algorithm [0.0]
最適化において、よく知られた古典的アルゴリズムの1つは電力反復である。
我々はこの落とし穴を回避するために量子化を提案する。
我々の手法はインスタンス非依存となり、量子コンピューティングの枠組みの中でブラックボックス最適化に対処することができる。
論文 参考訳（メタデータ） (2024-04-23T13:49:11Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - Learning the Positions in CountSketch [49.57951567374372]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。
本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-11T07:28:35Z) - A fast Multiplicative Updates algorithm for Non-negative Matrix Factorization [2.646309221150203]
本稿では,各サブプロブレムに対してヘッセン行列のより厳密な上界を構築することにより,乗法更新アルゴリズムの改善を提案する。
コンバージェンスはまだ保証されており、我々は実際に合成と実世界の両方のデータセットで、提案したfastMUアルゴリズムが通常の乗算更新アルゴリズムよりも数桁高速であることを示す。
論文 参考訳（メタデータ） (2023-03-31T12:09:36Z) - Batch-efficient EigenDecomposition for Small and Medium Matrices [65.67315418971688]
EigenDecomposition (ED)は多くのコンピュータビジョンアルゴリズムとアプリケーションの中心にある。
本稿では,コンピュータビジョンの応用シナリオに特化したQRベースのED手法を提案する。
論文 参考訳（メタデータ） (2022-07-09T09:14:12Z) - A quantum algorithm for solving eigenproblem of the Laplacian matrix of
a fully connected weighted graph [4.045204834863644]
完全連結重み付きグラフのラプラシア行列の固有確率を解くための効率的な量子アルゴリズムを提案する。
具体的には,ブロック符号化フレームワークに基づく最適ハミルトンシミュレーション手法を採用する。
また、このアルゴリズムは対称(非対称)正規化ラプラス行列の固有確率を解くために拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-03-28T02:24:08Z) - Fast Differentiable Matrix Square Root and Inverse Square Root [65.67315418971688]
微分可能な行列平方根と逆平方根を計算するためのより効率的な2つの変種を提案する。
前方伝搬には, Matrix Taylor Polynomial (MTP) を用いる方法と, Matrix Pad'e Approximants (MPA) を使用する方法がある。
一連の数値実験により、両方の手法がSVDやNSの繰り返しと比較してかなりスピードアップすることが示された。
論文 参考訳（メタデータ） (2022-01-29T10:00:35Z) - Sublinear Time Approximation of Text Similarity Matrices [50.73398637380375]
一般的なNystr"om法を不確定な設定に一般化する。
我々のアルゴリズムは任意の類似性行列に適用でき、行列のサイズでサブ線形時間で実行される。
本手法は,CUR分解の単純な変種とともに,様々な類似性行列の近似において非常によく機能することを示す。
論文 参考訳（メタデータ） (2021-12-17T17:04:34Z) - Non-PSD Matrix Sketching with Applications to Regression and
Optimization [56.730993511802865]
非PSDおよび2乗根行列の次元削減法を提案する。
複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
論文 参考訳（メタデータ） (2021-06-16T04:07:48Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Fast and Accurate Pseudoinverse with Sparse Matrix Reordering and
Incremental Approach [4.710916891482697]
擬逆は行列逆の一般化であり、機械学習で広く利用されている。
FastPIはスパース行列に対する新たなインクリメンタル特異値分解法(SVD)である。
我々は,FastPIが精度を損なうことなく,他の近似手法よりも高速に擬似逆計算を行うことを示す。
論文 参考訳（メタデータ） (2020-11-09T07:47:10Z) - Optimal Iterative Sketching with the Subsampled Randomized Hadamard
Transform [64.90148466525754]
最小二乗問題に対する反復スケッチの性能について検討する。
本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。
これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
論文 参考訳（メタデータ） (2020-02-03T16:17:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。