Fugu-MT 論文翻訳(概要): Continuous LWE

論文の概要: Continuous LWE

arxiv url: http://arxiv.org/abs/2005.09595v2
Date: Sat, 24 Oct 2020 20:55:35 GMT
ステータス: 処理完了
システム内更新日: 2022-12-01 13:39:02.067042
Title: Continuous LWE
Title（参考訳）: 連続LWE
Authors: Joan Bruna, Oded Regev, Min Jae Song, and Yi Tang
Abstract要約: CLWEと呼ばれるLearning with Errors(LWE)問題の連続的な類似点を紹介する。最短ケース格子問題の量子化をCLWEに与え、CLWEがLWEと同じような硬さの保証を享受していることを示す。
参考スコア（独自算出の注目度）: 32.345218864470446
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We introduce a continuous analogue of the Learning with Errors (LWE) problem, which we name CLWE. We give a polynomial-time quantum reduction from worst-case lattice problems to CLWE, showing that CLWE enjoys similar hardness guarantees to those of LWE. Alternatively, our result can also be seen as opening new avenues of (quantum) attacks on lattice problems. Our work resolves an open problem regarding the computational complexity of learning mixtures of Gaussians without separability assumptions (Diakonikolas 2016, Moitra 2018). As an additional motivation, (a slight variant of) CLWE was considered in the context of robust machine learning (Diakonikolas et al.~FOCS 2017), where hardness in the statistical query (SQ) model was shown; our work addresses the open question regarding its computational hardness (Bubeck et al.~ICML 2019).
Abstract（参考訳）: CLWEと呼ばれるLearning with Errors(LWE)問題の連続的な類似点を紹介する。最悪ケース格子問題から多項式時間量子還元をCLWEに与え、CLWEがLWEと同等の硬さを保証することを示す。あるいは、格子問題に対する新たな(量子)攻撃の道を開くと見ることもできる。我々の研究は、分離性仮定のないガウスの学習混合物の計算複雑性に関する未解決の問題を解決する(Diakonikolas 2016 Moitra 2018)。追加の動機として、統計クエリ(sq)モデルのハードネスが示されたロバストな機械学習(diakonikolas et al.~focs 2017)の文脈において、(わずかな変種である)clweが検討された。

関連論文リスト

Solving for X and Beyond: Can Large Language Models Solve Complex Math Problems with More-Than-Two Unknowns? [57.80779199039929]
大規模言語モデル (LLM) は数学問題の解法において顕著な性能を示した。本稿では,複数の未知の問題を組み込むことで,これらの制約に対処する新しいベンチマークであるBeyondXを紹介する。 BeyondXに関する実証的な研究によると、数学のタスクに特化して調整された既存のLLMの性能は、未知の数が増えるにつれて著しく低下する。
論文参考訳（メタデータ） (2024-07-06T17:01:04Z)
Investigating the Relation Between Problem Hardness and QUBO Properties [0.0]
この研究は、問題のプロパティ間の関係にいくつかの光を当てることを目的としている。機械学習、すなわちクラスタリングとサポートベクトルマシン(SVM)のトレーニングからよく知られた2つの問題を解析する。経験的評価は興味深い洞察を与え、クラスタリングQUBOインスタンスのスペクトルギャップがデータ分離可能性と正の相関を示す一方で、SVM QUBOでは逆が真であることを示す。
論文参考訳（メタデータ） (2024-04-03T13:53:03Z)
Clique Homology is QMA1-hard [0.0]
simplicial complex のホモロジー群を決定する決定問題は QMA1-hard である。これは、古典的と思われる問題は、実際には量子力学である可能性を示唆している。本稿では、トポロジカルデータ解析における量子優位性の問題への潜在的な影響について論じる。
論文参考訳（メタデータ） (2022-09-23T18:14:16Z)
Beyond Supervised Continual Learning: a Review [69.9674326582747]
連続学習(Continuous Learning, CL)は、定常データ分布の通常の仮定を緩和または省略する機械学習のフレーバーである。データ分布の変化は、いわゆる破滅的な忘れ(CF)効果、すなわち、過去の知識の突然の喪失を引き起こす可能性がある。本稿では、CLを他の環境で研究する文献をレビューする。例えば、監督を減らした学習、完全に教師なしの学習、強化学習などである。
論文参考訳（メタデータ） (2022-08-30T14:44:41Z)
Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures [11.348971335676444]
本稿では,誤り問題を伴う古典的学習と,その連続的なアナログであるCLWEとの間に直接的かつ概念的に簡易な還元効果を示す。これにより、CLWEのアプリケーションにLWEベースの暗号の強力な能力を持たせることができます。
論文参考訳（メタデータ） (2022-04-06T03:03:39Z)
Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
量子計算の2つのモデル: CQ_dとQC_d。 CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。 CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
論文参考訳（メタデータ） (2022-01-06T03:10:53Z)
Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。最近の研究は、低次手法のクラスに対する低い境界を確立している。意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文参考訳（メタデータ） (2021-12-07T18:50:17Z)
Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering [13.70673475846529]
以下の問題に対する時間量子アルゴリズムを示す。我々の主な貢献は、LWEに似た量子状態と興味深いパラメータをフィルタリング技術を用いて解くことである。
論文参考訳（メタデータ） (2021-08-25T02:23:37Z)
A New Constructive Heuristic driven by Machine Learning for the Traveling Salesman Problem [8.604882842499212]
近年,機械学習(ML)を用いてTSP(Traking Salesman Problem)を解くシステムでは,実ケースシナリオにスケールアップしようとすると問題が発生する。問題に対処するため、候補リスト(CL)の使用が提起されている。この作業では、高い確率のエッジに対してのみ、ソリューションの追加を確認するために、マシンラーニングモデルを使用します。
論文参考訳（メタデータ） (2021-08-17T21:37:23Z)
Disentangling Observed Causal Effects from Latent Confounders using Method of Moments [67.27068846108047]
我々は、軽度の仮定の下で、識別性と学習可能性に関する保証を提供する。我々は,線形制約付き結合テンソル分解に基づく効率的なアルゴリズムを開発し,スケーラブルで保証可能な解を得る。
論文参考訳（メタデータ） (2021-01-17T07:48:45Z)

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