Fugu-MT 論文翻訳(概要): Witness Complexity of Short Descriptions: A Cryptographic Perspective

論文の概要: Witness Complexity of Short Descriptions: A Cryptographic Perspective

arxiv url: http://arxiv.org/abs/2606.31370v1
Date: Tue, 30 Jun 2026 09:02:35 GMT
ステータス: 翻訳完了
システム内更新日: 2026-07-01 18:27:19.149181
Title: Witness Complexity of Short Descriptions: A Cryptographic Perspective
Title（参考訳）: 短い記述のウイットネス複雑性:暗号的視点
Abstract要約: 本稿では,チューリングマシン上での弦に近い記述に対する最小実行時間(gam(x))を導入することで,そのギャップを定式化する。第2部では,鍵や証明書の使い勝手の指標として,文法サイズと導出コストの非条件的ギャップを示す。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In cryptographic practice, where protocols impose strict time bounds, implementations demand predictable resource usage, and real-world systems require immediate verification for security and usability, a short key or certificate is useful only if it can be expanded or verified within a bounded time; otherwise a compact representation that requires superpolynomial work to expand offers no operational guarantee within a bounded-time protocol. This paper formalises that gap by introducing \emph{witness complexity} $\gam(x)$, the minimum running time over near-shortest descriptions of a string on a universal Turing machine. $\gam$ differs from Shannon entropy and Kolmogorov complexity $\KC$: low $\KC$ can coexist with high $\gam$. We prove invariance up to polynomial factors; a conditional separation (assuming $\PneqNP$). An unconditional lower bound from incomputability of $\KC$; a biconditional characterisation of $\PeqNP$ via the class-relative variant $\gP$; and polynomial-time tractability for structured $\classNP$ families. Part II develops companion measures and shows an unconditional gap between grammar size and derivation cost, positioning $\gam$ as a metric for the usability of keys and certificates.
Abstract（参考訳）: プロトコルが厳密な時間制限を課し、実装が予測可能なリソース使用を要求し、現実のシステムはセキュリティとユーザビリティの即時検証を必要とする場合、短い鍵または証明書は、制限時間内に拡張または検証できる場合にのみ有用である。本稿では,任意のチューリングマシン上での文字列のほぼ極小記述に対する最小実行時間である 'emph{witness complexity} $\gam(x)\ を導入することにより,そのギャップを定式化する。シャノンエントロピー (Shannon entropy) とコルモゴロフ複雑性 (Kolmogorov complexity) {\displaystyle \(\KC$: 低い $\KC$ は高い $\gam$ と共存することができる。多項式因子、条件分離( $\PneqNP$ を仮定する)まで不変性を証明する。非条件下限は $\KC$ の不計算性、クラス相対変数 $\gP$ による $\PeqNP$ の双条件的特徴付け、構造化された $\classNP$ 族に対する多項式時間トラクタビリティである。パートIIは、鍵や証明書の使いやすさの指標として $\gam$ を位置づけ、文法サイズと導出コストの間に無条件のギャップを示す。

関連論文リスト

When Does a Quantum Speedup Survive End-to-End? [0.0]
本稿では、量子インタフェースの宣言された実装パッケージに対して定義された転写レベル許容関係(A_Mpreceq_mathrmintA_Q)を紹介する。パッケージライセンスと同じ、どの適応的な古典的アクセストランスクリプトを、すべてのセットアップ、トランスクリプト生成、充電された精度のオーバーヘッドで識別する。
論文参考訳（メタデータ） (2026-09-09T08:06:26Z)
Prompting Complexity: Shortest Prompts for Texts and Behaviors in LLMs [1.9875440739965626]
固定命令調整言語モデルに対する複雑性の促進量を定義する。プログラムは任意のトークン文字列ではなく、可読な可読テキストに制限する。また、最も短い生成プロンプトと、仕様を満たす出力に到達するための行動的プロンプトの複雑さを比較することで、距離のプロンプトを定義する。
論文参考訳（メタデータ） (2026-07-07T11:12:44Z)
Probabilistically Checking Quantum Proofs, with Interaction [2.0482700732041397]
我々は、検証者および通信が共に量子オラクルであることが許される対話的証明(qIOP)の量子アナログについて研究する。我々の主な成果は、全通信が成り立つ言語に対するqIOPであるが、検証者は全キュービットの多元数のみを読み取る。
論文参考訳（メタデータ） (2026-06-08T14:59:51Z)
A Modular Approach to Succinct Arguments for QMA [17.20526790095253]
我々は、QMAの簡潔な議論の暗号的基礎を広げる新しいフレームワークを開発する。特に、LWEの硬さに依存しないQMAの最初の簡潔で古典的に検証可能な引数システムを得る。我々のコンパイラはZhang(QCrypt 25)の量子剛性に基づく通信圧縮技術を拡張している
論文参考訳（メタデータ） (2026-06-03T21:38:23Z)
Mitigating Bias in Locally Constrained Decoding via Tractable Proposals [73.78736135699953]
既存の局所的制約付き復号法は、ミオプティックに次のトークンを隠蔽することで制約を強制する。最近の研究では、シーケンシャルなモンテカルロ法を用いてバイアスを緩和しているが、効果的な提案分布や潜在的な関数を設計することは重要な課題である。我々は、$p_mathrmlm( cdot mid mathrmconstraint)$からSMCサンプリングのための提案とポテンシャルを構築するための一般的なアプローチを提案する。
論文参考訳（メタデータ） (2026-06-01T08:58:18Z)
Value Functions as Supermartingale Certificates [48.922124609307566]
適切な報酬の下では、$$-regularプロパティをほぼ確実に満足するポリシーに関連する値関数が、その仕様のStreet Supermartingale証明書を符号化していることを示す。我々の結果は有限マルコフ決定過程で実験的に検証され、有限で数え切れないほど無限で連続的な状態空間を保ち、RLによる証明書合成への原則的経路を示唆している。
論文参考訳（メタデータ） (2026-05-29T16:39:02Z)
Short-Context Dominance: How Much Local Context Natural Language Actually Needs? [48.429870236229696]
正確な全文予測を再現するのに必要となる最小コンテキスト長を計測する。長文文書から1-7kのトークンを持つシーケンスの場合、75-80%は最下位96トークンしか必要としない。そこで本研究では,実際の次点知識を必要としないMCL(Distributedally Aware MCL)の実践的プロキシについて紹介する。
論文参考訳（メタデータ） (2025-12-08T22:25:00Z)
A Verifier Hierarchy [1.006218778776515]
言語固有の検証時間を (f(n)) から (g(n)) に短縮するには,少なくとも (Omega(log(f(n) / g(n)))) の長さの証明書が必要であることを示す。この定理は証明複雑性に基づいた自然な階層を誘導する。
論文参考訳（メタデータ） (2025-07-31T12:42:42Z)
Single-pass Adaptive Image Tokenization for Minimum Program Search [75.59409288259151]
本稿では,単一前方通過における画像に対する適切なトークン数を予測する単一パス適応型トークン化器KARLを提案する。 KARLは、1回のパスで動作しながら、最近の適応トークン化器の性能と一致する。
論文参考訳（メタデータ） (2025-07-10T17:59:53Z)
Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
トークンの制約を評価するのは違法にコストがかかる LCDは文字列上のグローバル分布を歪め、ローカル情報のみに基づいてトークンをサンプリングすることができる。我々のアプローチは最先端のベースラインよりも優れていることを示す。
論文参考訳（メタデータ） (2025-04-07T18:30:18Z)
Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
我々は$f$-divergence-regularized offline policy learningを分析する。逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
論文参考訳（メタデータ） (2025-02-09T22:14:45Z)
Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
本稿では、よく知られたトランスフォーマーアーキテクチャを基盤とした、ランクの新たな特徴付けについて述べる。関数 $f$ のランクは、単一層変換器が要求する思考ステップの EmphChain の最小値に対応していることを示す。また、マルチヘッド単一層トランスをキャプチャするマルチヘッドランクの概念を導入し、有界なマルチヘッドランクを持つ関数クラスのPAC学習性の解析を行う。
論文参考訳（メタデータ） (2025-01-22T16:30:58Z)
Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
論文参考訳（メタデータ） (2021-07-28T04:28:55Z)
SafeComp: Protocol For Certifying Cloud Computations Integrity [0.0]
本稿では,この問題を制約下で解決するSafeCompという多人数対話型プロトコルを提案する。我々のプロトコルは、証明構築の複雑さを$O(n logn)$から$O(n)$に減らし、通信の複雑さを同等の長さの証明書を使って正確に1ラウンドにする。
論文参考訳（メタデータ） (2020-05-21T17:08:39Z)
Post-Quantum Cryptography(PQC): Generalized ElGamal Cipher over GL(8,F251) [0.0]
ポスト量子暗号(PQC)は、攻撃に耐性のある暗号プロトコルを見つけようとする。本稿では、一般化されたElGamal非軌道化プロトコルに基づく非対称暗号に焦点をあてる。
論文参考訳（メタデータ） (2017-02-12T22:50:28Z)

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

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