論文の概要: Improving Algorithmic Efficiency using Cryptography

• arxiv url: http://arxiv.org/abs/2502.13065v1
• Date: Tue, 18 Feb 2025 17:08:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-19 14:05:12.575237
• Title: Improving Algorithmic Efficiency using Cryptography
• Title（参考訳）: 暗号を用いたアルゴリズム効率の向上
• Authors: Vinod Vaikuntanathan, Or Zamir,
• Abstract要約: 計算問題を解く際の時間的複雑さを改善するために暗号を用いる方法を示す。 標準的な暗号仮定では、既存のアルゴリズムよりも高速なアルゴリズムを設計できることを示す。
• 参考スコア（独自算出の注目度）: 11.496343300483904
• License:
• 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, and (b) given a secret key, we can multiply such a n-by-n matrix with any vector in near-linear (in n) time. We provide constructions both over finite fields and the reals. This enables a broad speedup technique: any algorithm relying on a random matrix - such as those using various notions of dimensionality reduction - can replace it with a matrix from our distribution, achieving computational speedups while preserving correctness.
• Abstract（参考訳）: 暗号プリミティブは、ランダム性や相互作用の排除や削減など、様々な非暗号化目的に使用されている。 計算問題を解く際の時間的複雑さを改善するために暗号を用いる方法を示す。 具体的には、標準的な暗号仮定の下では、正確性を保ちながら、既存のアルゴリズムよりも漸近的に高速なアルゴリズムを設計できることを示す。 具体的な実演として、以下の性質を持つトラップドア行列の分布を構築する。 (a) 計算的に有界な敵は、この分布から引き出された行列とランダム行列を区別することができず、 b) 秘密鍵が与えられたとき、そのような n × n の行列を任意のベクトルに n に近い時間で乗算することができる。 有限体と実数に関する構成を提供する。 例えば、次元の減少という様々な概念を使っているアルゴリズムは、そのアルゴリズムを我々の分布から行列に置き換えることができ、正確性を保ちながら計算速度を上げることができる。

関連論文リスト

• 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)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  共分散行列の明示的な構成を避ける新しい推論手法を提案する。 本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。 いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
  論文  参考訳（メタデータ） (2022-02-25T16:35:26Z)
• Efficient GPU implementation of randomized SVD and its applications [17.71779625877989]
  行列分解は、次元データの圧縮やディープラーニングアルゴリズムなど、機械学習においてユビキタスである。 行列分解の典型的な解は、計算コストと時間を大幅に増大させる複雑さを持つ。 我々は,計算行列分解の計算負担を軽減するために,現代のグラフィカル処理ユニット(GPU)で並列に動作する効率的な処理操作を利用する。
  論文  参考訳（メタデータ） (2021-10-05T07:42:41Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

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

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