Structure of protocols for XOR functions
From MaRDI portal
Publication:4605274
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)