Query-to-Communication Lifting for BPP
From MaRDI portal
Publication:5117373
DOI10.1137/17M115339XzbMath1440.68092arXiv1703.07666OpenAlexW3048734876MaRDI QIDQ5117373
No author found.
Publication date: 25 August 2020
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1703.07666
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Communication complexity, information complexity (68Q11)
Related Items (11)
Communication complexity with small advantage ⋮ Structure of Protocols for XOR Functions ⋮ Dimension-free bounds and structural results in communication complexity ⋮ From Expanders to Hitting Distributions and Simulation Theorems ⋮ Simulation theorems via pseudo-random properties ⋮ Nondeterministic and randomized Boolean hierarchies in communication complexity ⋮ Unnamed Item ⋮ Query-to-Communication Lifting Using Low-Discrepancy Gadgets ⋮ Quantum versus randomized communication complexity, with efficient players ⋮ Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria ⋮ Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An information statistics approach to data stream and communication complexity
- Boolean function complexity. Advances and frontiers.
- Expressing combinatorial optimization problems by linear programs
- On the distributional complexity of disjointness
- Complexity measures and decision tree complexity: a survey.
- Towards proving strong direct product theorems
- Separation of the monotone NC hierarchy
- Communication complexity of approximate Nash equilibria
- Simulation theorems via pseudo-random properties
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
- Exponential separation of quantum and classical communication complexity
- Lower Bounds on the Size of Semidefinite Programming Relaxations
- The Sign-Rank of AC$^0$
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- The Pattern Matrix Method
- The Probabilistic Communication Complexity of Set Intersection
- Deterministic Communication vs. Partition Number
- Forrelation: A Problem That Optimally Separates Quantum from Classical Computing
- Structure of Protocols for XOR Functions
- Separations in Query Complexity Based on Pointer Functions
- Amortized Communication Complexity
- Communication Complexity
- An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
- Randomized Communication versus Partition Number
- Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
- Analysis of Boolean Functions
- Separations in query complexity using cheat sheets
- Entangled simultaneity versus classical interactivity in communication complexity
- Quantum one-way communication can be exponentially stronger than classical communication
- Rectangles Are Nonnegative Juntas
This page was built for publication: Query-to-Communication Lifting for BPP
