Structure of Protocols for XOR Functions
From MaRDI portal
Publication:4605274
DOI10.1137/17M1136869zbMATH Open1386.68062OpenAlexW2787163834MaRDI QIDQ4605274FDOQ4605274
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
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 Lp-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 (17)
- 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
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)
