scientific article

DOI10.4086/toc.2008.v004a007zbMath1213.68321OpenAlexW2138852390MaRDI QIDQ3002796

Emanuele Viola, Avi Wigderson

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

correlationlower boundcommunication complexitydirect productGowers normsmall-biasXOR Lemmageneralized inner productmultiparty protocolpolynomial over \(GF(2)\)

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (19)

A direct product theorem for two-party bounded-round public-coin communication complexity ⋮ A discrepancy lower bound for information complexity ⋮ Unnamed Item ⋮ Monomial Boolean functions with large high-order nonlinearities ⋮ A note on the relation between XOR and selective XOR lemmas ⋮ Unnamed Item ⋮ Limits of Boolean functions on \(\mathbb{F}_p^n\) ⋮ Interleaved Group Products ⋮ 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 ⋮ Unnamed Item ⋮ Simulation theorems via pseudo-random properties ⋮ New Strong Direct Product Results in Communication Complexity ⋮ Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates ⋮ On Yao’s XOR-Lemma ⋮ Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition ⋮ Pseudorandom Functions: Three Decades Later

This page was built for publication: