論文の概要: Improved Search-to-Decision Reduction for Random Local Functions
- arxiv url: http://arxiv.org/abs/2510.02944v1
- Date: Fri, 03 Oct 2025 12:39:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-06 16:35:52.378984
- Title: Improved Search-to-Decision Reduction for Random Local Functions
- Title（参考訳）: ランダム局所関数の探索・判定精度の向上
- Authors: Kel Zin Tan, Prashant Nalini Vasudevan,
- Abstract要約: $d$-ary predicate $P$で定義されるランダム局所関数は、各出力ビットが入力のランダムに選択されたビットに$P$を印加することで計算される関数である。
本稿では,任意の定数の述語によって定義されるランダム局所関数に対する新しい探索-決定還元法を提案する。
- 参考スコア（独自算出の注目度）: 3.029434408969759
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A random local function defined by a $d$-ary predicate $P$ is one where each output bit is computed by applying $P$ to $d$ randomly chosen bits of its input. These represent natural distributions of instances for constraint satisfaction problems. They were put forward by Goldreich as candidates for low-complexity one-way functions, and have subsequently been widely studied also as potential pseudo-random generators. We present a new search-to-decision reduction for random local functions defined by any predicate of constant arity. Given any efficient algorithm that can distinguish, with advantage $\epsilon$, the output of a random local function with $m$ outputs and $n$ inputs from random, our reduction produces an efficient algorithm that can invert such functions with $\tilde{O}(m(n/\epsilon)^2)$ outputs, succeeding with probability $\Omega(\epsilon)$. This implies that if a family of local functions is one-way, then a related family with shorter output length is family of pseudo-random generators. Prior to our work, all such reductions that were known required the predicate to have additional sensitivity properties, whereas our reduction works for any predicate. Our results also generalise to some super-constant values of the arity $d$, and to noisy predicates.
- Abstract（参考訳）: $d$-ary predicate $P$で定義されるランダム局所関数は、各出力ビットが入力のランダムに選択されたビットに$P$を印加することで計算される関数である。
これらは制約満足度問題に対するインスタンスの自然な分布を表す。
それらは低複素片方向函数の候補としてゴールドライヒによって提唱され、その後、擬似ランダム生成子としても広く研究されている。
本稿では,任意の定数の述語によって定義されるランダム局所関数に対する新しい探索-決定還元法を提案する。
有利な$\epsilon$と、$m$出力と$n$入力を持つランダム局所関数の出力を区別できる任意の効率的なアルゴリズムが与えられた場合、我々の還元は、$\tilde{O}(m(n/\epsilon)^2)$出力でそのような関数を逆転できる効率的なアルゴリズムを生成し、確率$\Omega(\epsilon)$で成功する。
これは、局所関数の族が一方向ならば、短い出力長を持つ関連族は擬ランダム生成子の族であることを意味する。
我々の研究に先立ち、既知の全ての還元は、述語が追加の感度特性を持つ必要があるのに対して、当社の還元は述語に対して機能する。
我々の結果は、arity $d$の超定数値や、ノイズのある述語にも一般化される。
関連論文リスト
- Rényi divergence-based uniformity guarantees for $k$-universal hash functions [59.90381090395222]
普遍ハッシュ関数は、ソースの出力を有限アルファベット上のランダム文字列にマッピングする。
ミンエントロピーによって測定されるように、ほぼ均一なランダムビットを蒸留することが可能であることを示す。
論文 参考訳（メタデータ） (2024-10-21T19:37:35Z) - A Pure Quantum Approximate Optimization Algorithm Based on CNR Operation [0.0]
汎用的な純粋量子近似最適化アルゴリズムを提案する。
このアルゴリズムは$p$レベルの分割・対数構造に構成されている。
2つの最適化問題の必要なキュービット数が10である場合、アルゴリズムの性能を詳細に示す。
論文 参考訳（メタデータ） (2023-10-27T06:54:39Z) - Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。
純粋な微分プライバシーのために、$K$-normメカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。
本稿では,総和,数,投票の単純な統計量について両問題を解く。
論文 参考訳（メタデータ） (2023-09-27T17:09:36Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - From Random Search to Bandit Learning in Metric Measure Spaces [7.168461603304643]
本稿ではランダム探索に関する理論的考察を行う。
基礎となる関数の風景を記述したエンフスキャッタリング次元の概念を導入する。
また、距離空間を2倍にするリプシッツ帯域に対して、BLiN-MOSと呼ばれるアルゴリズムを導入する。
論文 参考訳（メタデータ） (2023-05-19T08:18:49Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Randomized Exploration is Near-Optimal for Tabular MDP [45.16374124699648]
強化学習におけるThompson Sampling(TS)ライクアルゴリズムにおけるランダム化値関数を用いた探索について検討する。
1)1つのランダムシードを各エピソードで使用し、2)ベルンシュタイン型のノイズの大きさを算出すると、最悪の$widetildeOleft(HsqrtSATright)$リコールがエピソード時間非均質決定プロセスにバインドされることを示します。
論文 参考訳（メタデータ） (2021-02-19T01:42:50Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - Runtime Analysis of a Heavy-Tailed $(1+(\lambda,\lambda))$ Genetic
Algorithm on Jump Functions [9.853329403413701]
ジャンプ関数は、n(k + 1)/2k-k/2eO(k)$フィットネス評価のみの期待実行時に、ジャンプサイズ$k$で最適化できる。
ジャンプサイズが最大$n/4$のすべてのジャンプ関数上の分布パラメータを自然に選択したこのアルゴリズムは、前回の作業で得られる最良のインスタンス固有パラメータに近い性能を持つことを示す。
論文 参考訳（メタデータ） (2020-06-05T15:57:55Z) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。
我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。
次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文 参考訳（メタデータ） (2020-06-02T16:38:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。