論文の概要: Logspace Reducibility From Secret Leakage Planted Clique

• arxiv url: http://arxiv.org/abs/2107.11886v2
• Date: Wed, 8 Nov 2023 22:05:02 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-10 19:26:31.364018
• Title: Logspace Reducibility From Secret Leakage Planted Clique
• Title（参考訳）: シークレットリークプラントによるログスペースの低減
• Authors: Jay Mardia
• Abstract要約: 植民された傾斜問題は、計算現象を観察し、説明し、予測する文脈でよく研究されている。 この問題は、他の多くの統計問題のホストの計算困難さを推測するために用いられる。
• 参考スコア（独自算出の注目度）: 0.9427635404752933
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The planted clique problem is well-studied in the context of observing, explaining, and predicting interesting computational phenomena associated with statistical problems. When equating computational efficiency with the existence of polynomial time algorithms, the computational hardness of (some variant of) the planted clique problem can be used to infer the computational hardness of a host of other statistical problems. Is this ability to transfer computational hardness from (some variant of) the planted clique problem to other statistical problems robust to changing our notion of computational efficiency to space efficiency? We answer this question affirmatively for three different statistical problems, namely Sparse PCA, submatrix detection, and testing almost k-wise independence. The key challenge is that space efficient randomized reductions need to repeatedly access the randomness they use. Known reductions to these problems are all randomized and need polynomially many random bits to implement. Since we can not store polynomially many random bits in memory, it is unclear how to implement these existing reductions space efficiently. There are two ideas involved in circumventing this issue and implementing known reductions to these problems space efficiently. 1. When solving statistical problems, we can use parts of the input itself as randomness. 2. Secret leakage variants of the planted clique problem with appropriate secret leakage can be more useful than the standard planted clique problem when we want to use parts of the input as randomness. (abstract shortened due to arxiv constraints)
• Abstract（参考訳）: 植えられたクランク問題は、統計的問題に関連する興味深い計算現象を観察、説明、予測するという文脈でよく研究されている。 計算効率を多項式時間アルゴリズムの存在と同一視する場合、(いくつかの変種)植込みクリッド問題の計算硬度は、他の統計問題のホストの計算硬度を推測するために用いられる。 この能力は、計算効率の概念を宇宙効率に変化させるのに頑健な他の統計問題に(ある変種)植民された斜め問題から移すことができるだろうか? 我々は,スパースPCA,サブマトリクス検出,ほぼk-wise独立性テストという,3つの異なる統計問題に対して肯定的に回答する。 鍵となる課題は、空間効率のよいランダム化還元は、使用するランダム性に繰り返しアクセスする必要があることである。 これらの問題の既知の還元はすべてランダム化され、実装には多項式的に多くのランダムビットが必要である。 多項式的に多くのランダムビットをメモリに格納できないため、既存の還元空間を効率的に実装する方法は不明である。 この問題を回避し、これらの問題に対する既知の削減を実装するには、2つの考えがある。 1 統計問題を解く際、入力自体の一部をランダム性として用いることができる。 2 入力の一部をランダム性として使用したい場合、適切な秘密漏洩を伴う植込みクランク問題の秘密漏洩変種は、標準植込みクランク問題よりも有用である。 (arxiv制約により短縮)

関連論文リスト

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Regularized ERM on random subspaces [17.927376388967144]
  我々は、Nystromがカーネルメソッドに近づいた特殊なケースとして、データのランダムなサブセットにまたがるデータ依存部分空間を考える。 ランダムな部分空間を考えると自然に計算上の節約につながるが、問題は対応する学習精度が劣化するかどうかである。
  論文  参考訳（メタデータ） (2022-12-04T16:12:11Z)
• GRACE-C: Generalized Rate Agnostic Causal Estimation via Constraints [3.2374399328078285]
  時系列データから因果学習アルゴリズムによって推定される図形構造は、生成プロセスの因果時間スケールがデータの測定時間スケールと一致しない場合、誤解を招く因果情報を提供することができる。 既存のアルゴリズムは、この課題に対応するための限られたリソースを提供するため、研究者は彼らが知っているモデルを使うか、あるいは完全に因果学習を行う必要がある。 既存の方法は、(1)因果差と測定値の違いが知られていること、(2)時間スケールの違いが不明な場合にのみ非常に少数のランダム変数を扱うこと、(3)変数のペアにのみ適用されること、4)変数のペアにしか適用できないこと、など、四つの異なる欠点に直面している。
  論文  参考訳（メタデータ） (2022-05-18T22:38:57Z)
• An Application of a Multivariate Estimation of Distribution Algorithm to Cancer Chemotherapy [59.40521061783166]
  癌に対する化学療法治療は、多数の相互作用する変数と制約を持つ複雑な最適化問題である。 より洗練されたアルゴリズムは、このような複雑な問題に対してより良いパフォーマンスをもたらすことが示される。 我々は、この問題における多数の相互作用によって、より洗練されたアルゴリズムが妨げられていることが原因であると仮定する。
  論文  参考訳（メタデータ） (2022-05-17T15:28:46Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  我々は弱い教師付き回帰問題を解く。 weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。 数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
  論文  参考訳（メタデータ） (2021-04-13T23:21:01Z)
• Nonlinear Distribution Regression for Remote Sensing Applications [6.664736150040092]
  多くのリモートセンシングアプリケーションでは、観察から関心のある変数やパラメータを推定したい。 ニューラルネットワーク、ランダムフォレスト、ガウス過程などの標準アルゴリズムは、これら2つに関連して容易に利用可能である。 本稿では, グループ化されたデータの統計を仮定することなく, 従来の問題を解く非線形(カーネルベース)な分散回帰法を提案する。
  論文  参考訳（メタデータ） (2020-12-07T22:04:43Z)
• Resource Allocation in Multi-armed Bandit Exploration: Overcoming Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
  腕の引っ張りに様々な量の資源を割り当てることができる分割可能な資源にアクセス可能な場合,マルチアームの帯状地における探索について検討する。 特に、分散コンピューティングリソースの割り当てに重点を置いており、プル毎により多くのリソースを割り当てることで、結果をより早く得ることができます。
  論文  参考訳（メタデータ） (2020-10-31T18:19:29Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。 大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。 応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
  論文  参考訳（メタデータ） (2020-08-05T17:52:10Z)
• Faster Secure Data Mining via Distributed Homomorphic Encryption [108.77460689459247]
  ホモモルフィック暗号化(HE)は、最近、暗号化されたフィールド上で計算を行う能力により、ますます注目を集めている。 本稿では,スケーリング問題の解決に向けて,新しい分散HEベースのデータマイニングフレームワークを提案する。 各種データマイニングアルゴリズムとベンチマークデータセットを用いて,新しいフレームワークの有効性と有効性を検証する。
  論文  参考訳（メタデータ） (2020-06-17T18:14:30Z)
• Regularized ERM on random subspaces [18.541369654442796]
  我々は、データのランダムなサブセットにまたがるデータ依存部分空間を、カーネルメソッドに対するNystr"omアプローチの特別なケースとして、リカバリする可能性があると考えている。 ランダムな部分空間を考えると自然に計算上の節約につながるが、問題は対応する学習精度が劣化するかどうかである。
  論文  参考訳（メタデータ） (2020-06-17T17:21:33Z)
• Reducibility and Statistical-Computational Gaps from Secret Leakage [19.25775832101647]
  我々は, 秘密リークドライドドライド・ドライド(秘密リークドライド・ドライド・ドライド)の若干の一般化が, 様々な新しい平均ケース・リダクション技術をもたらすことを示した。 特定の種類の秘密漏れクランプに対する植込みクランプ予想の変種を用いて、厳密な統計計算トレードオフを導出する。
  論文  参考訳（メタデータ） (2020-05-16T20:56:09Z)

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

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