論文の概要: Monte Carlo to Las Vegas for Recursively Composed Functions

• arxiv url: http://arxiv.org/abs/2601.08073v1
• Date: Mon, 12 Jan 2026 23:34:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-14 18:27:18.98158
• Title: Monte Carlo to Las Vegas for Recursively Composed Functions
• Title（参考訳）: モンテカルロ、ラスベガスへ-再帰的な機能強化へ
• Authors: Bandar Al-Dhalaan, Shalev Ben-David,
• Abstract要約: 問合せ複雑性における一般測度の構成限界について検討する。 この極限は測度に関する合理的な仮定の下で収束することを示す。 次に、ランダム化されたクエリの複雑さの構成限界について驚くべき結果を与える。
• 参考スコア（独自算出の注目度）: 0.26709266817192023
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: For a (possibly partial) Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ as well as a query complexity measure $M$ which maps Boolean functions to real numbers, define the composition limit of $M$ on $f$ by $M^*(f)=\lim_{k\to\infty} M(f^k)^{1/k}$. We study the composition limits of general measures in query complexity. We show this limit converges under reasonable assumptions about the measure. We then give a surprising result regarding the composition limit of randomized query complexity: we show $R_0^*(f)=\max\{R^*(f),C^*(f)\}$. Among other things, this implies that any bounded-error randomized algorithm for recursive 3-majority can be turned into a zero-error randomized algorithm for the same task. Our result extends also to quantum algorithms: on recursively composed functions, a bounded-error quantum algorithm can be converted into a quantum algorithm that finds a certificate with high probability. Along the way, we prove various combinatorial properties of measures and composition limits.
• Abstract（参考訳）: ブール関数 $f\colon\{0,1\}^n\to\{0,1\}$ と、ブール関数を実数に写すクエリ複雑性測度 $M$ に対して、$M$ on $f$ by $M^*(f)=\lim_{k\to\infty} M(f^k)^{1/k}$ の合成極限を定義する。 問合せ複雑性における一般測度の構成限界について検討する。 この極限は測度に関する合理的な仮定の下で収束することを示す。 R_0^*(f)=\max\{R^*(f),C^*(f)\}$である。 このことは、再帰的な3重項に対する任意の有界エラーランダム化アルゴリズムを、同じタスクに対してゼロエラーランダム化アルゴリズムに変換することができることを意味している。 再帰的に構成された関数では、有界エラー量子アルゴリズムを量子アルゴリズムに変換し、高い確率で証明を見つけることができる。 その過程で、測度と構成限界の様々な組合せ的性質を証明した。

関連論文リスト

• Space-Efficient Quantum Error Reduction without log Factors [50.10645865330582]
  本稿では,多数決のランダムウォーク解釈に類似したライン上の重み付けウォークとして理解可能な,新たに単純化された浄化器の構成を提案する。 我々の浄化器は、前者よりも指数関数的に空間の複雑さが良く、精製されるアルゴリズムの音質-完全性ギャップに四分法的に依存している。
  論文  参考訳（メタデータ） (2025-02-13T12:04:39Z)
• On the Fine-Grained Query Complexity of Symmetric Functions [4.956977275061968]
  本稿では、Watrous予想のきめ細かいバージョンについて考察する。 確率が任意に1/2ドルに近いランダム化および量子化アルゴリズムを含む。
  論文  参考訳（メタデータ） (2023-09-20T13:04:45Z)
• 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)
• A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
  多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。 本稿では,差分に基づく探索法 (CombGapE) アルゴリズムを提案する。 我々は,CombGapEアルゴリズムが,合成データセットと実世界のデータセットの両方において,既存の手法を大幅に上回っていることを数値的に示す。
  論文  参考訳（メタデータ） (2023-06-15T15:37:31Z)
• On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
  我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。 我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
  論文  参考訳（メタデータ） (2023-03-20T08:17:32Z)
• Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)

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

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