論文の概要: Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case

• arxiv url: http://arxiv.org/abs/2109.02600v2
• Date: Tue, 21 Feb 2023 04:52:35 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-16 00:50:40.310261
• Title: Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case
• Title（参考訳）: マトリックス超収縮性, ストリーミングアルゴリズム, LDC--大文字の場合
• Authors: Srinivasan Arunachalam, Jo\~ao F. Doriguello
• Abstract要約: 大型アルファベット上で定義される行列値関数に対する超収縮的不等式を証明した。 逆数モデルの全てのストリーミングアルゴリズムが$(r-varepsilon)$-approximationを達成するためには、$Omega(n1-2/t)$量子空間が必要である。
• 参考スコア（独自算出の注目度）: 5.88864611435337
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We prove a hypercontractive inequality for matrix-valued functions defined over large alphabets, generalizing the result of Ben-Aroya, Regev, de Wolf (FOCS'08) for the Boolean alphabet. For such we prove a generalization of the $2$-uniform convexity inequality of Ball, Carlen, Lieb (Inventiones Mathematicae'94). Using our inequality, we present upper and lower bounds for the communication complexity of Hidden Hypermatching when defined over large alphabets, which generalizes the well-known Boolean Hidden Matching problem. We then consider streaming algorithms for approximating the value of Unique Games on a $t$-hyperedge hypergraph: an edge-counting argument gives an $r$-approximation with $O(\log{n})$ space. On the other hand, via our communication lower bound we show that every streaming algorithm in the adversarial model achieving a $(r-\varepsilon)$-approximation requires $\Omega(n^{1-2/t})$ quantum space. This generalizes the seminal work of Kapralov, Khanna, Sudan (SODA'15), and expand to the quantum setting results from Kapralov, Krachun (STOC'19) and Chou et al. (STOC'22). We next present a lower bound for locally decodable codes ($\mathsf{LDC}$) over large alphabets. An $\mathsf{LDC}$ $C:\mathbb{Z}_r^n\to \mathbb{Z}_r^N$ is an encoding of $x$ into a codeword in such a way that one can recover an arbitrary $x_i$ (with probability at least $1/r+\varepsilon$) by making a few queries to a corrupted codeword. The main question here is the trade-off between $N$ and $n$. Via hypercontractivity, we give an exponential lower bound $N= 2^{\Omega(\varepsilon^4 n/r^4)}$ for $2$-query (possibly non-linear) $\mathsf{LDC}$s over $\mathbb{Z}_r$ and using the non-commutative Khintchine inequality we improved our bound to $N= 2^{\Omega(\varepsilon^2 n/r^2)}$. Previously exponential lower bounds were known for $r=2$ (Kerenidis, de Wolf (JCSS'04)) and linear codes (Dvir, Shpilka (SICOMP'07)).
• Abstract（参考訳）: 我々は,大文字上で定義される行列値関数に対して,Ban-Aroya, Regev, de Wolf (FOCS'08) の結果を一般化し,超収縮的不等式を証明した。 そのため、ball, carlen, lieb (inventiones mathematicae'94) の2ドルの一様凸不等式を一般化することを証明する。 我々の不等式を用いて、大きなアルファベット上で定義された隠れたハイパーマッチングの通信複雑性の上限と下限を示し、有名なブール隠れマッチング問題を一般化する。 エッジカウント引数は$O(\log{n})$ spaceで$r$-approximationを与える。 一方、通信下界を介して、逆数モデルにおける全てのストリーミングアルゴリズムが$(r-\varepsilon)$-approximationを達成するには、$\Omega(n^{1-2/t})$量子空間が必要であることを示す。 これはカプラロフ、ハンナ、スーダン(SODA'15)の専門的な研究を一般化し、カプラロフ、クラチュン(STOC'19)、チョーら(STOC'22)の量子的設定結果にまで拡張する。 次に、大きなアルファベットに対して局所デオード可能な符号(\mathsf{LDC}$)の低い境界を示す。 $\mathsf{LDC}$$C:\mathbb{Z}_r^n\to \mathbb{Z}_r^N$は、任意の$x_i$(少なくとも1/r+\varepsilon$の確率で)をコードワードに変換するために$x$のエンコードである。 ここでの最大の疑問は、n$とn$の間のトレードオフである。 ハイパーコントラクティビティを通じて、指数下限の$n=2^{\omega(\varepsilon^4 n/r^4)}$を$$$-query(おそらく非線形)$\mathsf{ldc}$s over $\mathbb{z}_r$とし、非可換なkhintchine不等式を用いて、$n=2^{\omega(\varepsilon^2 n/r^2)}$にする。 以前は指数関数的な下界は$r=2$ (Kerenidis, de Wolf (JCSS'04)) と線形符号 (Dvir, Shpilka (SICOMP'07)) で知られていた。

関連論文リスト

• 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)

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

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