Structure of Protocols for XOR Functions
From MaRDI portal
Publication:4605274
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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
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 Lp-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