Structure of protocols for XOR functions

DOI10.1137/17M1136869MaRDI QIDQ4605274zbMATH OpenOpenAlexFDO

Authors Hamed Hatami, Kaave Hosseini, Shachar Lovett

Publication date 22 February 2018

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/17m1136869

zbMATH Keywords

communication complexityXOR functionparity decision tree

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• Communication complexities of symmetric XOR functions
• Parity decision tree complexity and 4-party communication complexity of XOR-functions are polynomially equivalent
• Efficient quantum protocols for XOR functions
• Norms, XOR lemmas, and lower bounds for polynomials and protocols
• Tight bounds on communication complexity of symmetric XOR functions in one-way and SMP models

Cites work

• scientific article; zbMATH DE number 2159066 (Why is no real title available?)
• A probabilistic technique for finding almost-periods of convolutions
• Arithmetic progressions in sumsets and \(L^p\)-almost-periodicity
• Communication complexity and combinatorial lattice theory
• Deterministic communication vs. partition number
• Efficient quantum protocols for XOR functions
• Green's sumset problem at density one half
• On the Bogolyubov-Ruzsa lemma
• On the degree of Boolean functions as real polynomials
• On the parity complexity measures of Boolean functions
• Parity decision tree complexity and 4-party communication complexity of XOR-functions are polynomially equivalent
• Query-to-communication lifting for BPP
• Roth's theorem for four variables and additive structures in sums of sparse sets
• Separation of the monotone NC hierarchy
• Testing Fourier dimensionality and sparsity
• The pattern matrix method

Cited in

(21)

• A composition theorem for randomized query complexity
• Communication complexities of symmetric XOR functions
• Query-to-communication lifting for BPP using inner product
• Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
• A generalization of a theorem of Rothschild and van Lint
• Parity decision tree complexity and 4-party communication complexity of XOR-functions are polynomially equivalent
• Dimension-free bounds and structural results in communication complexity
• Simulation theorems via pseudo-random properties
• Approximate F_2-Sketching of Valuation Functions
• A short list of equalities induces large sign-rank
• Query-to-communication lifting for BPP
• Counting the number of perfect matchings, and generalized decision trees
• Quantum versus randomized communication complexity, with efficient players
• Query-to-communication lifting using low-discrepancy gadgets
• On the Decision Tree Complexity of Threshold Functions
• Efficient quantum protocols for XOR functions
• Randomized versus deterministic decision tree size
• From expanders to hitting distributions and simulation theorems
• A generalization of a theorem of Rothschild and van Lint
• Lifting Theorems for Equality
• Norms, XOR lemmas, and lower bounds for polynomials and protocols

This page was built for publication: Structure of protocols for XOR functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4605274)