Structure of Protocols for XOR Functions

DOI10.1137/17M1136869zbMath1386.68062OpenAlexW2787163834MaRDI QIDQ4605274

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

Related Items (16)

On the Decision Tree Complexity of Threshold Functions ⋮ A Short List of Equalities Induces Large Sign-Rank ⋮ Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\) ⋮ Query-to-Communication Lifting for BPP ⋮ Dimension-free bounds and structural results in communication complexity ⋮ Approximate F_2-Sketching of Valuation Functions ⋮ From Expanders to Hitting Distributions and Simulation Theorems ⋮ Simulation theorems via pseudo-random properties ⋮ A generalization of a theorem of Rothschild and van Lint ⋮ Counting the number of perfect matchings, and generalized decision trees ⋮ A generalization of a theorem of Rothschild and van Lint ⋮ Lifting Theorems for Equality ⋮ Query-To-Communication Lifting for BPP Using Inner Product ⋮ Query-to-Communication Lifting Using Low-Discrepancy Gadgets ⋮ Quantum versus randomized communication complexity, with efficient players ⋮ A Composition Theorem for Randomized Query Complexity

Cites Work

• Unnamed Item
• Unnamed Item
• A probabilistic technique for finding almost-periods of convolutions
• On the parity complexity measures of Boolean functions
• Communication complexity and combinatorial lattice theory
• On the degree of Boolean functions as real polynomials
• On the Bogolyubov-Ruzsa lemma
• Separation of the monotone NC hierarchy
• On the structure of Boolean functions with small spectral norm
• ROTH’S THEOREM FOR FOUR VARIABLES AND ADDITIVE STRUCTURES IN SUMS OF SPARSE SETS
• Green's sumset problem at density one half
• The Pattern Matrix Method
• Deterministic Communication vs. Partition Number
• Arithmetic Progressions in Sumsets and L^p-Almost-Periodicity
• Query-to-Communication Lifting for BPP
• Efficient quantum protocols for XOR functions
• Testing Fourier Dimensionality and Sparsity

This page was built for publication: Structure of Protocols for XOR Functions