Structure of protocols for XOR functions
From MaRDI portal
Publication:4605274
DOI10.1137/17M1136869zbMATH Open1386.68062OpenAlexW2787163834MaRDI QIDQ4605274FDOQ4605274
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
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
Measures of information, entropy (94A17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)
Cites Work
- On the degree of Boolean functions as real polynomials
- The pattern matrix method
- Testing Fourier dimensionality and sparsity
- Communication complexity and combinatorial lattice theory
- A probabilistic technique for finding almost-periods of convolutions
- On the structure of Boolean functions with small spectral norm
- Title not available (Why is that?)
- Separation of the monotone NC hierarchy
- On the Bogolyubov-Ruzsa lemma
- Efficient quantum protocols for XOR functions
- On the parity complexity measures of Boolean functions
- Arithmetic progressions in sumsets and \(L^p\)-almost-periodicity
- Roth's theorem for four variables and additive structures in sums of sparse sets
- Green's sumset problem at density one half
- Deterministic Communication vs. Partition Number
- Query-to-Communication Lifting for BPP
- Parity decision tree complexity and 4-party communication complexity of XOR-functions are polynomially equivalent
Cited In (19)
- A Short List of Equalities Induces Large Sign-Rank
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
- A generalization of a theorem of Rothschild and van Lint
- Query-to-Communication Lifting for BPP
- Dimension-free bounds and structural results in communication complexity
- Approximate F_2-Sketching of Valuation Functions
- Simulation theorems via pseudo-random properties
- Query-to-Communication Lifting Using Low-Discrepancy Gadgets
- From Expanders to Hitting Distributions and Simulation Theorems
- Counting the number of perfect matchings, and generalized decision trees
- Quantum versus randomized communication complexity, with efficient players
- Query-To-Communication Lifting for BPP Using Inner Product
- A Composition Theorem for Randomized Query Complexity
- On the Decision Tree Complexity of Threshold Functions
- Randomized versus deterministic decision tree size
- A generalization of a theorem of Rothschild and van Lint
- Lifting Theorems for Equality
- Norms, XOR lemmas, and lower bounds for polynomials and protocols
- Communication complexities of symmetric XOR functions
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)
