Fugu-MT 論文翻訳(概要): A Note on Hardness of Computing Recursive Teaching Dimension

論文の概要: A Note on Hardness of Computing Recursive Teaching Dimension

arxiv url: http://arxiv.org/abs/2307.09792v1
Date: Wed, 19 Jul 2023 07:17:06 GMT
ステータス: 処理完了
システム内更新日: 2023-07-20 15:06:11.272201
Title: A Note on Hardness of Computing Recursive Teaching Dimension
Title（参考訳）: 再帰的指導次元計算の硬さに関する一考察
Authors: Pasin Manurangsi
Abstract要約: 指数時間仮説(ETH)を仮定して,概念クラスに対する再帰的教育次元(RTD)の計算には$nOmega(log n)$-timeが必要であることを示す。これは問題に対するブルートフォースアルゴリズムの実行時間$nO(log n)$と一致する。
参考スコア（独自算出の注目度）: 28.57552551316786
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this short note, we show that the problem of computing the recursive teaching dimension (RTD) for a concept class (given explicitly as input) requires $n^{\Omega(\log n)}$-time, assuming the exponential time hypothesis (ETH). This matches the running time $n^{O(\log n)}$ of the brute-force algorithm for the problem.
Abstract（参考訳）: 本稿では,概念クラスに対する再帰的教育次元(RTD)の計算には,指数時間仮説(ETH)を仮定して,$n^{\Omega(\log n)}$-timeが必要であることを示す。これは問題に対するブルートフォースアルゴリズムの実行時間$n^{O(\log n)}$と一致する。

関連論文リスト

Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
論文参考訳（メタデータ） (2024-08-10T04:26:19Z)
Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。 EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
論文参考訳（メタデータ） (2023-10-23T18:26:00Z)
Longest Common Substring and Longest Palindromic Substring in $\tilde{\mathcal{O}}(\sqrt{n})$ Time [0.0]
LCS(Longest Common Substring)とLPS(Longest Palindromic Substring)は、コンピュータ科学における古典的な問題である。計算回路モデルにおいて, LCS と LPS の双方に対する量子アルゴリズムを提案する。
論文参考訳（メタデータ） (2023-09-03T19:27:57Z)
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)
From Bit-Parallelism to Quantum String Matching for Labelled Graphs [0.0]
二次時間で解ける多くの問題は、ビットパラレルのスピードアップが$w$で、$w$はコンピュータワードサイズである。このような制限されたグラフの族上の単純なビット並列アルゴリズムは、現実的な量子アルゴリズムに変換可能であることを示す。
論文参考訳（メタデータ） (2023-02-06T15:14:34Z)
Solving a Special Type of Optimal Transport Problem by a Modified Hungarian Algorithm [2.1485350418225244]
本稿では,特殊な輸送問題 (OT) について検討し,それを正確に解くための改良されたハンガリーのアルゴリズムを提案する。 m$と$n$の原子を持つ辺り間のOT問題に対して、提案アルゴリズムの計算複雑性は$O(m2n)$である。
論文参考訳（メタデータ） (2022-10-29T16:28:46Z)
Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文参考訳（メタデータ） (2022-06-07T18:00:01Z)
Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文参考訳（メタデータ） (2022-04-13T22:18:47Z)
Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文参考訳（メタデータ） (2021-11-09T16:50:18Z)
Fast Classical and Quantum Algorithms for Online $k$-server Problem on Trees [0.19573380763700712]
木上の$k$サーバ問題に対するオンラインアルゴリズムを検討する。 Chrobak と Larmore は最適な競合比を持つこの問題に対して$k$-competitive アルゴリズムを提案した。本稿では,前処理に要するO(nlog n)$時間複雑性を持つ新しい時間効率アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-08-01T14:21:45Z)
Classical and Quantum Algorithms for Constructing Text from Dictionary Problem [0.0]
辞書(小文字列列)からテキストを構築する際の問題の解法について検討する。この問題はバイオインフォマティクスに応用され、小さな断片から長いDNA配列を再構築するSequenceアセンブリー法と関係がある。
論文参考訳（メタデータ） (2020-05-28T22:44:01Z)

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