Fugu-MT 論文翻訳(概要): Open Problem: Average-Case Hardness of Hypergraphic Planted Clique Detection

論文の概要: Open Problem: Average-Case Hardness of Hypergraphic Planted Clique Detection

arxiv url: http://arxiv.org/abs/2009.05870v1
Date: Sat, 12 Sep 2020 21:55:32 GMT
ステータス: 処理完了
システム内更新日: 2022-10-19 07:59:19.749729
Title: Open Problem: Average-Case Hardness of Hypergraphic Planted Clique Detection
Title（参考訳）: オープン問題:ハイパーグラフィック植込みクランク検出における平均硬度
Authors: Yuetian Luo and Anru R. Zhang
Abstract要約: HPC検出の計算困難性のさらなる証拠が開発できるかどうかを問う。特に、HPCとPC検出の計算硬度が等価かどうかを推測する。
参考スコア（独自算出の注目度）: 3.8073142980733
License: http://creativecommons.org/licenses/by-sa/4.0/
Abstract: We note the significance of hypergraphic planted clique (HPC) detection in the investigation of computational hardness for a range of tensor problems. We ask if more evidence for the computational hardness of HPC detection can be developed. In particular, we conjecture if it is possible to establish the equivalence of the computational hardness between HPC and PC detection.
Abstract（参考訳）: 我々は, 様々なテンソル問題に対する計算困難性の検討において, ハイパーグラフィック植込みクランク(hpc)検出の意義について考察する。 HPC検出の計算困難性のさらなる証拠が開発できるかどうかを問う。特に、hpcとpc検出の間の計算困難性の同値性を確立することができるかどうかを推測する。

関連論文リスト

On additive error approximations to #BQP [0.34089646689382486]
我々は、#BQPとして知られる数え上げクラスの量子一般化に対する加法近似について研究する。まず,#BQP問題に対する加算近似を,対応する検証回路における証人量子ビット数の誤差指数に近似する効率的な量子アルゴリズムが存在することを示す。
論文参考訳（メタデータ） (2024-11-04T20:51:20Z)
Detection and Identification Accuracy of PCA-Accelerated Real-Time Processing of Hyperspectral Imagery [0.0]
検出率に顕著な変化が現れる前に、主成分の数を相当減らすことができる。 ACEを用いて検出し, 確率, スペクトルを同定し, 主成分数を大幅に削減し, 検出率に顕著な変化がみられた。
論文参考訳（メタデータ） (2023-11-23T02:36:29Z)
Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing [93.83016310295804]
AQCは研究関心の問題を実装でき、コンピュータビジョンタスクのための量子表現の開発に拍車をかけた。本研究では,この情報を確率的バランスの取れたk平均クラスタリングに活用する可能性について検討する。最適でない解を捨てる代わりに, 計算コストを少なくして, 校正後部確率を計算することを提案する。これにより、合成タスクと実際の視覚データについて、D-Wave AQCで示すような曖昧な解とデータポイントを識別することができる。
論文参考訳（メタデータ） (2023-10-18T17:59:45Z)
HD-Bind: Encoding of Molecular Structure with Low Precision, Hyperdimensional Binary Representations [3.3934198248179026]
超次元計算(HDC)は、低精度二進ベクトル算術を活用できる学習パラダイムである。本稿では,HDCに基づく推論手法が,より複雑な機械学習手法よりも90倍効率が高いことを示す。
論文参考訳（メタデータ） (2023-03-27T21:21:46Z)
Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
グラフ編集距離(GED: Graph Edit Distance)は、2つのグラフ間の(異なる)相似性の度合いを測定する。本稿では、GED計算における2つの量子アプローチの比較研究について述べる。
論文参考訳（メタデータ） (2021-11-19T12:35:26Z)
Lung Cancer Lesion Detection in Histopathology Images Using Graph-Based Sparse PCA Network [93.22587316229954]
ヘマトキシリンとエオシン(H&E)で染色した組織学的肺スライドにおける癌病変の自動検出のためのグラフベーススパース成分分析(GS-PCA)ネットワークを提案する。我々は,SVM K-rasG12D肺がんモデルから得られたH&Eスライダーの精度・リコール率,Fスコア,谷本係数,レシーバ演算子特性(ROC)の曲線下領域を用いて,提案アルゴリズムの性能評価を行った。
論文参考訳（メタデータ） (2021-10-27T19:28:36Z)
Statistical and computational thresholds for the planted $k$-densest sub-hypergraph problem [13.808053718325635]
我々は,$d$-uniform ハイパーグラフ上に$k$-densest サブハイパーグラフを植え付けることで回復する問題を考察する。この根本的な問題は、例えば、コミュニティの検出、平均ケースの複雑さ、神経科学の応用など、様々な文脈に現れる。
論文参考訳（メタデータ） (2020-11-23T16:02:12Z)
Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
論文参考訳（メタデータ） (2020-08-05T17:52:10Z)
The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise [67.27523616312428]
分布非依存型PACモデルにおけるハーフスペースの逆強正則学習の計算複雑性について検討する。この問題に対して,計算効率のよい学習アルゴリズムとほぼ一致する計算硬度結果を与える。
論文参考訳（メタデータ） (2020-07-30T04:18:51Z)
Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits [9.427635404752936]
我々は2つのクラスタリングモデル、定数高階クラスタリング(CHC)とランク1高階クラスタリング(ROHC)に焦点を当てる。我々は,CHCとROHCの検出/回復が統計的に可能である信号対雑音比の境界を同定する。信号対雑音比がしきい値以上である場合に、信頼性の高い検出と回復を実現するアルゴリズムを提案する。
論文参考訳（メタデータ） (2020-05-21T15:53:44Z)
On estimating the entropy of shallow circuit outputs [49.1574468325115]
確率分布と量子状態のエントロピーを推定することは情報処理の基本的な課題である。本稿では,有界ファンインと非有界ファンアウトのゲートを持つ対数深度回路か定数深度回路のいずれかによって生成された分布や状態に対するエントロピー推定が,少なくともLearning with Errors問題と同程度難しいことを示す。
論文参考訳（メタデータ） (2020-02-27T15:32:08Z)

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