論文の概要: Direct sum theorems beyond query complexity

• arxiv url: http://arxiv.org/abs/2408.15570v1
• Date: Wed, 28 Aug 2024 06:53:29 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-29 17:03:09.229150
• Title: Direct sum theorems beyond query complexity
• Title（参考訳）: クエリ複雑性を超えた直和定理
• Authors: Daiki Suruga,
• Abstract要約: 古典的/量子的クエリの複雑さを拡張する新しいフレームワークを導入する。 この枠組みの中で、いくつかの基本的な直和定理を確立する。 関数 $f: 0, 1k to 0, 1$ と小さなエラー $varepsilon > 0$ が存在して、$n$インスタンスを同時に解決するには、クエリの複雑さが $tildeO(nsqrtk)$ である。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A fundamental question in computer science is: \emph{Is it harder to solve $n$ instances independently than to solve them simultaneously?} This question, known as the direct sum question or direct sum theorem, has been paid much attention in several research fields. Despite its importance, however, little has been discovered in many other research fields. In this paper, we introduce a novel framework that extends to classical/quantum query complexity, PAC-learning for machine learning, statistical estimation theory, and more. Within this framework, we establish several fundamental direct sum theorems. The main contributions of this paper include: (i) establishing a complete characterization of the amortized query/oracle complexities, and (ii) proving tight direct sum theorems when the error is small. Note that in our framework, every oracle access needs to be performed \emph{classically} even in the quantum setting. This can be thought of one limitation of this work. As a direct consequence of our results, we obtain the following: (A) The first known asymptotic separation of the randomized query complexity. Specifically, we show that there is a function $f: \{0, 1\}^k \to \{0, 1\}$ and small error $\varepsilon > 0$ such that solving $n$ instances simultaneously requires the query complexity $\tilde{O}(n\sqrt{k})$ but solving one instance with the same error has the complexity $\tilde{\Omega}(k)$. In communication complexity this type of separation was previously given in~Feder, Kushilevitz, Naor and Nisan (1995). (B) The query complexity counterpart of the ``information = amortized communication" relation, one of the most influential results in communication complexity shown by Braverman and Rao (2011) and further investigated by Braverman (2015). We hope that our results will provide further interesting applications in the future.
• Abstract（参考訳）: コンピュータ科学の根本的な疑問は以下のとおりである。 \emph{II}$n$インスタンスを同時に解決するよりも、独立して解決することが難しいか? 直和問題または直和定理として知られるこの問題は、いくつかの研究分野において大きな注目を集めている。 しかし、その重要性にもかかわらず、他の多くの研究分野ではほとんど発見されていない。 本稿では,古典的/量子的クエリ複雑性,機械学習のためのPAC学習,統計的推定理論などを拡張する新しいフレームワークを提案する。 この枠組みの中で、いくつかの基本的な直和定理を確立する。 本論文の主な貢献は以下のとおりである。 一 償却されたクエリ/オークルの複雑さの完全な特徴を確立すること。 (ii)誤差が小さいとき、厳密な直和定理を証明すること。 私たちのフレームワークでは、全てのオラクルアクセスは、量子設定においても、emph{classically} で実行する必要があることに注意してください。 これはこの研究の限界の一つと考えることができる。 結果の直接的な結果として, (A) ランダム化クエリの複雑性の漸近的分離が最初に知られている。 具体的には、関数 $f: \{0, 1\}^k \to \{0, 1\}$ および小さなエラー $\varepsilon > 0$ が存在して、同時に$n$ のインスタンスを解くには、クエリの複雑さ $\tilde{O}(n\sqrt{k})$ を必要とするが、同じエラーで1つのインスタンスを解くことは、複雑さ $\tilde{\Omega}(k)$ の複雑さを持つ。 コミュニケーションの複雑さにおいて、このタイプの分離は以前はFeder, Kushilevitz, Naor and Nisan (1995) で与えられていた。 (B)'information = amortized communication'関係とは,Braverman and Rao (2011) が示し,Braverman (2015) がさらに検討したコミュニケーション複雑性の最も影響力のある結果の1つである。 将来的には、さらなる興味深いアプリケーションを提供したいと思っています。

関連論文リスト

• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。 クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
  論文  参考訳（メタデータ） (2023-12-27T15:50:47Z)
• Robust Approximation Algorithms for Non-monotone $k$-Submodular Maximization under a Knapsack Constraint [0.0]
  2つの決定論的近似アルゴリズムは、knapsack制約の下での非単調な$k$-部分モジュラー複雑性の問題に対して提案される。 提案アルゴリズムは,非単調な目的に対して,O(nk)$クエリの計算量内で一定の近似比を提供する。
  論文  参考訳（メタデータ） (2023-09-21T12:42:52Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。 我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
  論文  参考訳（メタデータ） (2023-06-28T16:33:39Z)
• Randomised Composition and Small-Bias Minimax [0.9252523881586053]
  クエリ複雑性に関する2つの結果が、$mathrmR(f)$であることを示す。 まず、「線形化」複雑性測度$mathrmLR$を導入し、内部衝突合成定理を満たすことを示す: $mathrmR(f) geq Omega(mathrmR(f) mathrmLR(g))$ for all partial $f$と$g$。
  論文  参考訳（メタデータ） (2022-08-26T23:32:19Z)
• Matrix Discrepancy from Quantum Communication [13.782852293291494]
  我々は,不一致の最小化と(量子)通信複雑性の新たな関連性を開発する。 対称$n times n$$A_1,ldots,A_n$ with $|A_i| leq 1$ and $|A_i|_F leq n1/4$ に対し、pm 1n において $sum_i leq n x_i A_i$ の最大固有値が最大となる符号 $x が存在することを示す。
  論文  参考訳（メタデータ） (2021-10-19T16:51:11Z)
• Circuit Complexity in $\mathcal{Z}_{2}$ ${\cal EEFT}$ [1.3177888879666482]
  我々は$mathcalZ$ Even Effective Field Theories の回路複雑性を計算する。 我々は、高階ウィルソン作用素を持つ巨大な自由体論を考える。 この研究はほとんどのガウス諸国で行われている。
  論文  参考訳（メタデータ） (2021-09-20T18:00:04Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。 情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
  論文  参考訳（メタデータ） (2020-12-17T16:43:11Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries [55.28642461328172]
  平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。 我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
  論文  参考訳（メタデータ） (2020-06-25T19:59:24Z)
• Towards Optimal Separations between Quantum and Randomized Query Complexities [0.30458514384586394]
  入力に対して2O(k)$クエリを行うことで量子アルゴリズムを解くことができることを示す。 任意の定数 $varepsilon>0$ に対して、$O(1)$ 対 $N2/3-varepsilon$ 分離を与える。
  論文  参考訳（メタデータ） (2019-12-29T01:42:31Z)

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

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