Fugu-MT 論文翻訳(概要): Randomized query complexity can beat certificate complexity

論文の概要: Randomized query complexity can beat certificate complexity

arxiv url: http://arxiv.org/abs/2609.15063v1
Date: Mon, 14 Sep 2026 05:29:42 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-16 07:15:06.096523
Title: Randomized query complexity can beat certificate complexity
Title（参考訳）: ランダム化されたクエリの複雑さが証明書の複雑さを上回る
Abstract要約: R(f) = O(sqrtC(f)) の関数を構成する。同じ関数はまた、$Q(f) = O(C(f)1/4) を持ち、Q(f) は f の有界エラー量子クエリ複雑性である。
参考スコア（独自算出の注目度）: 1.7889544416325804
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: A long-standing open question in query complexity asks whether there is a total Boolean function f with R(f) << C(f), where R(f) and C(f) denote its bounded-error randomized query complexity and certificate complexity, respectively. We construct a function with R(f) = O~(sqrt{C(f)}), which is optimal up to log factors. The same function also has $Q(f) = O~(C(f)^{1/4}), where Q(f) is the bounded-error quantum query complexity of f, which is also nearly optimal.
Abstract（参考訳）: 問合せ複雑性における長年のオープンな疑問は、R(f) <<C(f) を持つブール関数 f が存在するかどうかを問うものである。 R(f) = O~(sqrt{C(f)}) の関数を構成する。同じ関数は、$Q(f) = O~(C(f)^{1/4} でもあり、Q(f) は f の有界エラー量子クエリ複雑性であり、これもほぼ最適である。

関連論文リスト

A Near-Quartic Separation Between Certificate Complexity and Quantum Query Complexity [0.0]
合計ブール関数$f$, $Q(f) = widetildeO(sqrt[4]C(f))$, $Q(f)$は有界エラー量子クエリ複雑性を示し、$C(f)$は証明複雑性を表す。
論文参考訳（メタデータ） (2026-09-10T15:04:28Z)
How Hard is it to Decide if a Fact is Relevant to a Query? [1.6058099298620423]
データベース D が与えられたとき、ブール共役クエリ (CQ) q と D の事実 f は、f が q wrt に関連するかどうかを決定する。自己結合(同じ関係を持つ複数の原子)を犯人とみなす。この結果から,クエリ評価よりも関連性の判断が困難であることや,効率のよい関連性計算を許容するクエリの自然クラスを同定した。
論文参考訳（メタデータ） (2026-04-24T10:29:27Z)
Monte Carlo to Las Vegas for Recursively Composed Functions [0.26709266817192023]
問合せ複雑性における一般測度の構成限界について検討する。この極限は測度に関する合理的な仮定の下で収束することを示す。次に、ランダム化されたクエリの複雑さの構成限界について驚くべき結果を与える。
論文参考訳（メタデータ） (2026-01-12T23:34:37Z)
Non-Asymptotic Length Generalization [26.982645261213847]
理想化された設定において、様々な関数のクラスに対する長さ一般化の証明可能な保証を提供する。本稿では,最小複雑度補間器学習アルゴリズムが最適長複雑性を実現することを示す。
論文参考訳（メタデータ） (2025-06-03T17:09:34Z)
Efficient and Scalable Neural Symbolic Search for Knowledge Graph Complex Query Answering [50.1887329564127]
複雑なクエリに対する効率的でスケーラブルなシンボル検索フレームワークを提案する。我々のフレームワークは、ほぼ同じ性能を維持しながら、シンボリックメソッドの計算負荷を90%削減する。
論文参考訳（メタデータ） (2025-05-13T01:24:09Z)
Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文参考訳（メタデータ） (2023-06-28T16:33:39Z)
The Role of Symmetry in Quantum Query-to-Communication Simulation [3.517404936232172]
量子設定におけるO(log n)オーバーヘッドはいくつかの関数に対して必要であり、したがってBCWシミュレーションは厳密であることを示す。また、BCWシミュレーションでは、ログnのオーバーヘッドが要求される関数を構成するための一般的なレシピも提供する。
論文参考訳（メタデータ） (2020-12-09T18:58:55Z)
On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。私たちの後悔の限界はエピソードの数とは無関係です。
論文参考訳（メタデータ） (2020-11-09T18:32:22Z)
Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文参考訳（メタデータ） (2020-09-18T02:18:44Z)
Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
論文参考訳（メタデータ） (2020-06-21T15:32:21Z)
Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting [81.70513857417106]
CascadeBAIを設計し、分析する。これは、$K$アイテムのベストセットを見つけるアルゴリズムである。 CascadeBAIの時間的複雑さの上限は、決定的な分析課題を克服することによって導かれる。その結果,カスケードBAIの性能は,時間的複雑性の低い境界の導出により,いくつかの実践的状況において最適であることが示唆された。
論文参考訳（メタデータ） (2020-01-23T16:47:52Z)

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