What is it about?
We prove a hypercontractive inequality for matrix-valued functions defined over large alphabets $\mathbb{Z}_r$ and employ it to obtain new results on various topics: streaming algorithms, communication complexity, and locally decodable codes
Featured Image
Why is it important?
Our matrix-valued hypercontractive inequality is not only novel, but follows from a simple application of the 2 -uniform convexity inequality of Ball, Carlen, Lieb (Inventiones Mathematicae'94), meaning that powerful results can still be obtained from long standard tools. Armed with our new inequality, we further characterise the limitations and separations between classical and quantum computation and communication in solving important problems: communication complexity of Hidden Hypermatching and streaming algorithms for approximating the value of Unique Games.
Perspectives
We hope that our matrix-valued hypercontractive inequality finds more applications in computer science, since standard Boolean hypercontractivity has been an ubiquitous tool in the field for the past 20 or so years.
João Doriguello
HUN-REN Alfréd Rényi Institute of Mathematics
Read the Original
This page is a summary of: Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case, ACM Transactions on Computation Theory, August 2024, ACM (Association for Computing Machinery),
DOI: 10.1145/3688824.
You can read the full text:
Contributors
The following have contributed to this page
