Publication:3002796
From MaRDI portal
DOI10.4086/toc.2008.v004a007zbMath1213.68321MaRDI QIDQ3002796
Publication date: 24 May 2011
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4086/toc.2008.v004a007
correlation; lower bound; communication complexity; direct product; Gowers norm; small-bias; XOR Lemma; generalized inner product; multiparty protocol; polynomial over \(GF(2)\)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Interleaved Group Products, Unnamed Item, Pseudorandom Functions: Three Decades Later, Unnamed Item, Unnamed Item, Monomial Boolean functions with large high-order nonlinearities, A direct product theorem for two-party bounded-round public-coin communication complexity, A discrepancy lower bound for information complexity, Limits of Boolean functions on \(\mathbb{F}_p^n\), The NOF multiparty communication complexity of composed functions, The communication complexity of addition, One-way multiparty communication lower bound for pointer jumping with applications, Improved direct product theorems for randomized query complexity, A note on the relation between XOR and selective XOR lemmas, Simulation theorems via pseudo-random properties, New Strong Direct Product Results in Communication Complexity, Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition, Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates, On Yao’s XOR-Lemma
