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)).
翻译:以大字母定义的矩阵值函数, 我们证明我们非常不平等。 以大字母定义的隐藏超配值, 将已知的布尔值隐藏匹配问题普遍化。 然后, 我们考虑以接近美元超高的高压字母( FOCS'08) 来计算Unal- Alform( FOCS'08) 。 对于这样的我们证明, 球、 Carllen、 Lieb( 创造数学94) 的2美元统一等同不平等性。 利用我们的不平等, 我们展示了隐藏超配的通信复杂性, 以大字母定义定义来定义已知的布尔值隐藏匹配问题。 然后, 我们考虑以美元超市价的算法来计算Unal- 美元超市值游戏值( NRCS.