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
- 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 (21)
- 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
- Approximate F_2-Sketching of Valuation Functions
- Simulation theorems via pseudo-random properties
- 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
- A composition theorem for randomized query complexity
- Query-to-communication lifting for BPP using inner product
- 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)
