論文の概要: 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)) で知られていた。

関連論文リスト

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

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

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