Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case
| Autor: | Arunachalam, Srinivasan, Doriguello, João F. |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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)). Comment: 41 pages. v2: several changes; 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 |
| Databáze: | arXiv |
| Externí odkaz: |
|