Matrix hypercontractivity, streaming algorithms and LDCs: the large
alphabet case
- URL: http://arxiv.org/abs/2109.02600v2
- Date: Tue, 21 Feb 2023 04:52:35 GMT
- Title: Matrix hypercontractivity, streaming algorithms and LDCs: the large
alphabet case
- Authors: Srinivasan Arunachalam, Jo\~ao F. Doriguello
- Abstract summary: We prove a hypercontractive inequality for matrix-valued functions defined over large alphabets.
We show that every streaming algorithm in the adversarial model achieving a $(r-varepsilon)$-approximation requires $Omega(n1-2/t)$ quantum space.
- Score: 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)).
Related papers
- Fast, robust approximate message passing [2.668787455520979]
We give a fast, spectral procedure for implementing approximate-message passing (AMP) algorithms robustly.
Our algorithm performs a spectral pre-processing step and mildly modifies the perturbeds of $mathcal A$.
arXiv Detail & Related papers (2024-11-05T03:20:14Z) - The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$.
As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
arXiv Detail & Related papers (2024-10-26T06:21:42Z) - Fast swap regret minimization and applications to approximate correlated
equilibria [20.047624953965965]
For any constant $varepsilon>0$, our algorithm obtains $varepsilon T$-swap regret within only $T = mathsfpolylog(n)$ rounds.
Our algorithm has an exponential dependence on $varepsilon$, but we prove a new, matching lower bound.
arXiv Detail & Related papers (2023-10-30T15:35:24Z) - Area law for the maximally mixed ground state in degenerate 1D gapped
systems [5.088702935364181]
We show an area law with logarithmic correction for the maximally mixed state $Omega$ in the (degenerate) ground space of a 1D gapped local Hamiltonian $H$.
We also get an area law for the mutual information of the form $mathrmI(L:R)_Omega leq O(log |L|)$.
arXiv Detail & Related papers (2023-10-29T14:36:30Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem.
The goal is to approximate $mathbfA$ as a product of low-rank factors.
Our techniques generalize to other common variants of the BMF problem.
arXiv Detail & Related papers (2023-06-02T18:55:27Z) - Query-optimal estimation of unitary channels in diamond distance [3.087385668501741]
We consider process tomography for unitary quantum channels.
We output a classical description of a unitary that is $varepsilon$-close to the unknown unitary in diamond norm.
arXiv Detail & Related papers (2023-02-27T19:00:00Z) - Quantum and classical low-degree learning via a dimension-free Remez
inequality [52.12931955662553]
We show a new way to relate functions on the hypergrid to their harmonic extensions over the polytorus.
We show the supremum of a function $f$ over products of the cyclic group $exp(2pi i k/K)_k=1K$.
We extend to new spaces a recent line of work citeEI22, CHP, VZ22 that gave similarly efficient methods for learning low-degrees on hypercubes and observables on qubits.
arXiv Detail & Related papers (2023-01-04T04:15:40Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations.
The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
arXiv Detail & Related papers (2022-06-17T17:55:43Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
arXiv Detail & Related papers (2020-08-24T06:50:57Z) - Streaming Complexity of SVMs [110.63976030971106]
We study the space complexity of solving the bias-regularized SVM problem in the streaming model.
We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
arXiv Detail & Related papers (2020-07-07T17:10:00Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.