論文の概要: Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case
- arxiv url: http://arxiv.org/abs/2109.02600v3
- Date: Mon, 11 Nov 2024 17:43:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-14 19:24:40.879469
- Title: Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case
- Title（参考訳）: マトリックス超収縮性, ストリーミングアルゴリズム, LDC--大文字の場合
- Authors: Srinivasan Arunachalam, Joao F. Doriguello,
- Abstract要約: We consider streaming algorithm for Approximating the value of Unique Games on a hypergraph with $t$-size hyperedges。
この値の$(r-varepsilon)$-approximationを達成する逆モデルの全てのストリーミングアルゴリズムは、$Omega(n1-2/t)$量子空間を必要とする。
- 参考スコア（独自算出の注目度）: 3.729242965449096
- License:
- Abstract: We prove a hypercontractive inequality for matrix-valued functions defined over large alphabets. In order to do so, we prove a generalization of the powerful $2$-uniform convexity inequality for trace norms of Ball, Carlen, Lieb (Inventiones Mathematicae'94). Using our hypercontractive~inequality, we present upper and lower bounds for the communication complexity of the Hidden Hypermatching problem defined over large alphabets. We then consider streaming algorithms for approximating the value of Unique Games on a hypergraph with $t$-size hyperedges. By using our communication lower bound, we show that every streaming algorithm in the adversarial model achieving an $(r-\varepsilon)$-approximation of this value requires $\Omega(n^{1-2/t})$ quantum space, where $r$ is the alphabet size. We next present a lower bound for locally decodable codes (LDC) $\mathbb{Z}_r^n\to \mathbb{Z}_r^N$ over large alphabets with recoverability probability at least $1/r + \varepsilon$. Using hypercontractivity, we give an exponential lower bound $N = 2^{\Omega(\varepsilon^4 n/r^4)}$ for $2$-query (possibly non-linear) LDCs over $\mathbb{Z}_r$ and using the non-commutative Khintchine inequality we prove an improved lower bound of $N = 2^{\Omega(\varepsilon^2 n/r^2)}$.
- Abstract（参考訳）: 大型アルファベット上で定義される行列値関数に対する超収縮的不等式を証明した。
そのため、ボール、カーレン、リーブ(InInventiones Mathematicae'94)のトレースノルムに対して、強力な2$一様凸不等式を一般化する。
大文字上で定義された隠れハイパーマッチング問題の通信複雑性の上限と下限を示す。
次に,$t$サイズのハイパーエッジを持つハイパーグラフ上で,Unique Gamesの価値を近似するストリーミングアルゴリズムを検討する。
この値の$(r-\varepsilon)$-approximationには$\Omega(n^{1-2/t})$量子空間が必要で、r$はアルファベットサイズである。
次に、復調確率が少なくとも1/r + \varepsilon$の大きいアルファベットに対して、局所復調可能符号 (LDC) $\mathbb{Z}_r^n\to \mathbb{Z}_r^N$ に対する下界を示す。
超収縮性を用いて、指数的下界の$N = 2^{\Omega(\varepsilon^4 n/r^4)}$を$$$-query(おそらく非線形) LDCsを$\mathbb{Z}_r$で与え、非可換なKhintchine不等式を用いて、$N = 2^{\Omega(\varepsilon^2 n/r^2)}$を改良した下界の$Nを証明した。
関連論文リスト
- Fast, robust approximate message passing [2.668787455520979]
本稿では,AMPアルゴリズムを頑健に実装するための高速なスペクトル計算法を提案する。
提案アルゴリズムはスペクトル前処理のステップを実行し,$mathcal A$の摂動を緩やかに修正する。
論文 参考訳（メタデータ） (2024-11-05T03:20:14Z) - The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Fast swap regret minimization and applications to approximate correlated
equilibria [20.047624953965965]
任意の定数$varepsilon>0$に対して、我々のアルゴリズムは$varepsilon T$-swap regretを$T = Mathsfpolylog(n)$ roundsで取得する。
我々のアルゴリズムは$varepsilon$に指数関数的依存を持つが、我々は一致する新しい下界を証明している。
論文 参考訳（メタデータ） (2023-10-30T15:35:24Z) - Area law for the maximally mixed ground state in degenerate 1D gapped
systems [5.088702935364181]
我々は、最大混合状態$Omega$に対する対数補正を伴う領域法則を、1Dギャップ化された局所ハミルトニアン$H$の(縮退した)基底空間で示す。
また、$mathrmI(L:R)_Omega leq O(log |L|)$という形の相互情報に対して面積法則を得る。
論文 参考訳（メタデータ） (2023-10-29T14:36:30Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Query-optimal estimation of unitary channels in diamond distance [3.087385668501741]
単一量子チャネルのプロセストモグラフィーについて考察する。
我々は、ダイヤモンドノルムの未知のユニタリに$varepsilon$-closeのユニタリの古典的な記述を出力する。
論文 参考訳（メタデータ） (2023-02-27T19:00:00Z) - Quantum and classical low-degree learning via a dimension-free Remez
inequality [52.12931955662553]
ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。
巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。
我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
論文 参考訳（メタデータ） (2023-01-04T04:15:40Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - 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) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。