論文の概要: 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を証明した。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
  未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。 我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。 このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
  論文  参考訳（メタデータ） (2024-02-22T02:20:24Z)
• 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)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• 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)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem [4.549831511476248]
  すべてのブール関数に対して、$f$, $bullet quad mathrmdeg(f) = O(widetildemathrmdeg(f)2)$:$f$の次数は、f$の近似次数において最も自明な二次数であることを示す。 f$ がその隣接行列で指定される $n$-頂点グラフの非単調グラフ特性であるならば、$mathrmQ(f)=Omega(n)$ もまた最適である。
  論文  参考訳（メタデータ） (2020-10-23T19:21:28Z)
• 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)
• A Direct Product Theorem for One-Way Quantum Communication [6.891238879512672]
  一般関係 $fsubseteqmathcalXtimesmathcalYtimesmathcalZ$ の一方交絡支援量子通信複雑性に対する直積定理を証明する。 私たちが知っている限りでは、これは量子通信に対する最初の直接積定理である。
  論文  参考訳（メタデータ） (2020-08-20T13:31:41Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)

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

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