Fugu-MT 論文翻訳(概要): A Survey on Complexity Measures of Pseudo-Random Sequences

論文の概要: A Survey on Complexity Measures of Pseudo-Random Sequences

arxiv url: http://arxiv.org/abs/2405.08479v3
Date: Sun, 28 Jul 2024 16:04:48 GMT
ステータス: 処理完了
システム内更新日: 2024-07-30 23:08:22.000809
Title: A Survey on Complexity Measures of Pseudo-Random Sequences
Title（参考訳）: 擬似乱数列の複雑さ対策に関する調査
Authors: Chunlei Li,
Abstract要約: 1960年代に2進列のコルモゴロフ複雑性が導入されて以来、ランダムネス評価のための複雑性測定のトピックにおいて大きな進歩があった。本調査は, 擬似ランダム列の線形, 二次, 最大次複雑度に関する過去40年間の顕著な研究をレビューする。
参考スコア（独自算出の注目度）: 2.6530332965939345
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Since the introduction of the Kolmogorov complexity of binary sequences in the 1960s, there have been significant advancements in the topic of complexity measures for randomness assessment, which are of fundamental importance in theoretical computer science and of practical interest in cryptography. This survey reviews notable research from the past four decades on the linear, quadratic and maximum-order complexities of pseudo-random sequences and their relations with Lempel-Ziv complexity, expansion complexity, 2-adic complexity, and correlation measures.
Abstract（参考訳）: 1960年代に2進数列のコルモゴロフ複雑性が導入されて以降、理論計算機科学や暗号学における実践的関心の中心であるランダム性評価の複雑さ尺度のトピックにおいて、大きな進歩があった。本調査では, 擬似ランダム列の線形, 二次, 最大次複雑度と, レンペル・ジブ複雑性, 拡張複雑性, 2進複雑性, 相関測定との関係について, 過去40年間の顕著な研究をレビューした。

関連論文リスト

The 4-adic complexity of quaternary sequences with low autocorrelation and high linear complexity [0.0]
我々は,低自己相関と高線形複雑性を持つ新しい4進列の4進複雑性を推定する。以上の結果から,これらの系列は有理近似アルゴリズムの攻撃に抵抗するため,大きく4進的複雑であることがわかった。
論文参考訳（メタデータ） (2024-01-06T12:38:41Z)
Spread complexity in saddle-dominated scrambling [0.0]
本研究では, サーモフィールド二重状態の拡散複雑性について考察した。 Lanczosアルゴリズムを適用すると、これらのシステムにおける拡散複雑性が、エンフェーシス系を連想させる特徴を示すことが判明した。
論文参考訳（メタデータ） (2023-12-19T20:41:14Z)
A relation between Krylov and Nielsen complexity [0.0]
クリロフ複雑性とニールセン複雑性は量子進化複雑性の定量化に成功している。 2つの量の間に関係があることが示される。すなわち、状態進化のクリロフ複雑性の時間平均は、ある行列のトレースとして表すことができる。
論文参考訳（メタデータ） (2023-11-30T09:51:22Z)
An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。本稿では,差分探索アルゴリズム (CombGapE) を提案する。
論文参考訳（メタデータ） (2023-06-15T15:37:31Z)
Evolution of circuit complexity in a harmonic chain under multiple quenches [0.0]
複数のクエンチのシナリオでは、複雑さは他の情報理論の指標と比べて明らかに異なる振る舞いを示す。連続したクエンチを多数適用することにより、時間発展状態の複雑さを高い値に増大させることができることを示す。このモデルはまた、異なる時間で実行された2つの連続したクエンチ間の複雑さの交叉という興味深い現象を示す。
論文参考訳（メタデータ） (2022-06-07T14:59:26Z)
Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
我々はPMDPsの新しいサブクラスについて研究し、その潜在状態は、最近の短い長さ$m$の履歴によって復号化することができる。特に、リッチ・オブザーブレーション・セッティングにおいて、指数関数的にスケールするサンプル複雑性を持つ新しい「モーメントマッチング」アプローチを用いて、新しいアルゴリズムを開発する。以上の結果から,これらの環境下での強化学習には短期記憶が十分であることが示唆された。
論文参考訳（メタデータ） (2022-02-08T16:39:57Z)
On the Complexity of a Practical Primal-Dual Coordinate Method [63.899427212054995]
ランダム・座標降下法(PURE-CD)を用いた原始双対アルゴリズムの複雑性境界を証明した。バイマックス性能問題を解くための優れた外挿が得られることが示されている。
論文参考訳（メタデータ） (2022-01-19T16:14:27Z)
Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms [55.41644538483948]
特に、状態準備および読み出しプロセスのような実装のいくつかのステップは、アルゴリズム自体の複雑さの側面を超越することができる。本稿では、方程式の線形系と微分方程式の線形系を解くための量子アルゴリズムの完全な実装に関わる複雑性について述べる。
論文参考訳（メタデータ） (2021-06-23T16:33:33Z)
Majorizing Measures, Sequential Complexities, and Online Learning [2.1793134762413433]
本稿では, シーケンシャルなRademacher複雑性を制御するために, ジェネリックチェアリングと大規模化手法を導入する。分数被覆数の概念は, 逐次スケール感応次元の点で支配的であることを示す。我々は最悪のシーケンシャルなRademacher複雑性に対して、厳密な収縮不等式を確立する。
論文参考訳（メタデータ） (2021-02-02T19:52:58Z)
Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes [60.479499225746295]
本稿では,ガウス過程に対して,パラメータ空間全体に対して同時に保持可能な保証付きスケーラブルな近似を導入する。我々の近似は、スパーススペクトルガウス過程(SSGP)のための改良されたサンプル複雑性解析から得られる。
論文参考訳（メタデータ） (2020-11-17T05:41:50Z)
Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning? [108.94173231481355]
長い地平線を計画する学習は、エピソード強化学習問題における中心的な課題である。長地平線RLは、少なくともミニマックス感覚において、短地平線RLよりも困難ではないことを示す。
論文参考訳（メタデータ） (2020-05-01T17:56:38Z)

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