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)}$.
v2: close to published version; the overall text was improved, references were added, LDC lower bound was improved, the PIR bound in Result 7 was corrected to due an error
Hypercontractive inequalities for real-valued functions over the Boolean cube play an important role in theoretical computer science. In this work, 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. To obtain our result we prove a generalization of the powerful $2$-uniform convexity inequality for trace norms of Ball, Carlen, Lieb (Inventiones Mathematicae'94). We give two applications of this hypercontractive inequality.
Locally decodable codes: we present a lower bound for locally decodable codes (LDC) over large alphabets. An LDC $C:\mathbb{Z}_r^n\to \mathbb{Z}_r^N$ is an encoding of $x\in \mathbb{Z}_r^n$ into a codeword $C(x)$ in such a way that one can recover an arbitrary $x_i\in \mathbb{Z}_r$ (with probability at least $1/r+\varepsilon$) by making only a few queries to a corrupted codeword. The main question in LDCs is the trade-off between $N$ and $n$. By 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$. Previously exponential lower bounds were known for $r=2$ (Kerenidis and de Wolf (JCSS'04)) and for \emph{linear} codes (Dvir and Shpilka (SICOMP'07)).
Streaming algorithms: we present upper and lower bounds for the communication complexity of the Hidden Hypermatching problem 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: in this direction a simple edge-counting argument gives an $r$-approximation with $O(\log n)$ space. On the other hand, we use our communication lower bound to show that every streaming algorithm in the adversarial model achieving a $(r-\varepsilon)$-approximation of this value requires $\Omega(n^{1-1/t})$ classical space or $\Omega(n^{1-2/t})$ quantum space. In this setting, these results simplify and generalize the seminal work of Kapralov, Khanna and Sudan (SODA'15) and Kapravol and Krachun (STOC'19) for the case $r=2$.
