Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case
From MaRDI portal
Cites work
- scientific article; zbMATH DE number 1574603 (Why is no real title available?)
- scientific article; zbMATH DE number 2019623 (Why is no real title available?)
- scientific article; zbMATH DE number 3442634 (Why is no real title available?)
- scientific article; zbMATH DE number 7053293 (Why is no real title available?)
- scientific article; zbMATH DE number 3073200 (Why is no real title available?)
- scientific article; zbMATH DE number 7651028 (Why is no real title available?)
- scientific article; zbMATH DE number 7650072 (Why is no real title available?)
- 2-server PIR with subpolynomial communication
- A new exponential separation between quantum and classical one-way communication complexity
- A simple semi-streaming algorithm for global minimum cuts
- A spectral gap precludes low-dimensional embeddings
- A tight lower bound for restricted PIR protocols
- Advances in Cryptology - EUROCRYPT 2004
- Almost optimal super-constant-pass streaming lower bounds for reachability
- An introduction to matrix concentration inequalities
- An optimal space lower bound for approximating MAX-CUT
- Analysis of Boolean Functions
- Approximability of all finite CSPs with linear sketches
- Automata, Languages and Programming
- Constant depth circuits, Fourier transform, and learnability
- Efficient and error-correcting data structures for membership and polynomial evaluation
- Embedding the diamond graph in L_p and dimension reduction in L₁
- Expander graphs and their applications
- Exponential lower bound for 2-query locally decodable codes via a quantum argument
- Exponential separation of quantum and classical one-way communication complexity
- Exponential separations for one-way quantum communication complexity, with applications to cryptography
- Hypercontractivity of simple random variables
- Inequalities in Fourier analysis
- Linear space streaming lower bounds for approximating CSPs
- Locally decodable codes
- Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits
- Logarithmic Sobolev Inequalities
- Lower bounds for (batch) PIR with private preprocessing
- Lower bounds for linear locally decodable codes and private information retrieval
- On matrix rigidity and locally self-correctable codes
- On the efficiency of local decoding procedures for error-correcting codes
- On the hardness of approximating minimum vertex cover
- On the uniform convexity of L^p and l^p
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Optimal hypercontractivity for Fermi fields and related non-commutative integration inequalities
- Optimal streaming approximations for all Boolean Max-2CSPs and Max-kSAT
- Optimum bounds for the distributions of martingales in Banach spaces
- Outlaw distributions and locally decodable codes
- Private information retrieval
- Private vs. common random bits in communication complexity
- Quantum lower bounds by polynomials
- Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
- Sharp uniform convexity and smoothness inequalities for trace norms
- Some Applications of Coding Theory in Computational Complexity
- Some applications of hypercontractive inequalities in quantum information theory
- Streaming Lower Bounds for Approximating MAX-CUT
- Streaming complexity of approximating Max 2CSP and Max Acyclic Subgraph
- The complex convexity of quasi-normed linear spaces
- The quantum and classical streaming complexity of quantum and classical Max-Cut
- The space complexity of approximating the frequency moments
- The streaming complexity of cycle counting, sorting by reversals, and other problems
- The theory of quantum information
- Tight Lower Bounds for 2-query LCCs over Finite Fields
- Time-uniform Chernoff bounds via nonnegative supermartingales
- (1 + (1))-approximation to MAX-CUT requires linear space
- Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
This page was built for publication: Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7022377)
