論文の概要: (Implicitly) Characterizing Probabilistic Polynomial Time as Used in Cryptography
- arxiv url: http://arxiv.org/abs/2610.14739v1
- Date: Sat, 10 Oct 2026 08:58:23 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-20 12:00:47.240099
- Title: (Implicitly) Characterizing Probabilistic Polynomial Time as Used in Cryptography
- Title（参考訳）: 暗号における確率的多項式時間の特徴付け
- Abstract要約: 最近導入された$$-calculus for randomized calculation($mathbfBLL$)は、一階および二階のポリ時間計算の概念を正確に捉えることができることを示す。
その結果、$mathbfBLL$は、暗号化で使われる実験や敵を表現するのに十分強力であることを示している。
- 参考スコア（独自算出の注目度）: 0.6445605125467574
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we show how a recently introduced $λ$-calculus for randomized computation, called $λ\mathbf{BLL}$, can accurately capture the notions of first- and second-order polytime computations used in cryptographic definitions and proofs. These results, spelled out in the style of so-called \emph{implicit computational complexity}, imply that $λ\mathbf{BLL}$ is sufficiently powerful to express experiments and adversaries as used in cryptography, and that reductions, when formulated within the calculus, are guaranteed to be complexity-preserving. Remarkably, while polynomial-time soundness holds for the full calculus, polynomial-time completeness already follows in presence of a minimal finite set of basic functions.
- Abstract（参考訳）: 本稿では、最近導入された$λ$-calculus for randomized calculation(英語版)である$λ\mathbf{BLL}$が、暗号定義や証明に使用される一階および二階のポリ時間計算の概念を正確に捉えることができることを示す。
これらの結果は、いわゆる「emph{implicit compute complexity}」のスタイルで書かれており、$λ\mathbf{BLL}$は、暗号で使われる実験や逆数を表現するのに十分強力であり、計算機内で定式化された場合、複雑性を保存することが保証される。
興味深いことに、多項式時間完全性は全積分に対して成り立つが、多項式時間完全性は基本関数の最小限の有限集合の存在下で既に従っている。
関連論文リスト
- From Hilbert's Tenth Problem to Quantum Speedup: Explicit Oracles for Bounded Diophantine Systems [0.0]
我々は、有界整数領域上のディオファント方程式を解くために、完全に可逆的なアルゴリズムフレームワークを導入する。
抽象ブラックボックスの仮定を超えて、この明示的なアーキテクチャ合成は、必要な量子演算が有界なオーバーヘッドとして働くことを保証している。
論文 参考訳（メタデータ） (2026-05-13T18:01:01Z) - Learning Intersections of Two Margin Halfspaces under Factorizable Distributions [56.51474048985742]
ハーフスペースの交叉学習は計算学習理論における中心的な問題である。
たった2つのハーフスペースであっても、学習が時間内に可能かどうかという大きな疑問が残る。
本稿ではCSQ硬度障壁を確実に回避する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-11-13T00:28:24Z) - Quantum Advantage via Efficient Post-processing on Qudit Classical Shadow tomography [3.040305634723913]
計算量と記憶量の両方を削減できるquditシャドウトモグラフィーに基づく量子的アプローチを提案する。
(operatornametr(rho O)) は (textpoly(log d)) 計算で効率的に推定できる。
論文 参考訳（メタデータ） (2024-08-29T03:56:16Z) - Complementary polynomials in quantum signal processing [0.0]
与えられた$P$を実装するには、まず対応する補完的な$Q$を構築しなければならない。
この問題に対する既存のアプローチでは、明示的な誤り解析には適さない数値的手法が採用されている。
複素解析を用いた補体系に対する新しいアプローチを提案する。
論文 参考訳（メタデータ） (2024-06-06T16:47:11Z) - 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) - Optimal Randomized Approximations for Matrix based Renyi's Entropy [16.651155375441796]
整数次数$alpha$の場合のランダム近似と非整数$alpha$の場合の直列近似を開発する。
大規模シミュレーションと実世界の応用は、開発した近似の有効性を検証する。
論文 参考訳（メタデータ） (2022-05-16T02:24:52Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳（メタデータ） (2020-11-09T18:32:22Z) - SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
SURFは分布を断片的に近似するアルゴリズムである。
実験では最先端のアルゴリズムよりも優れています。
論文 参考訳（メタデータ） (2020-02-22T01:03:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。