Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)

DOI10.1007/s00037-018-0175-5zbMath1425.68127OpenAlexW2604847700WikidataQ128850510 ScholiaQ128850510MaRDI QIDQ2422767

Yanyan Li

Publication date: 20 June 2019

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-018-0175-5

zbMATH Keywords

communicationliftingquery\(\mathsf{P}^{\mathsf{NP}}\)

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

A Short List of Equalities Induces Large Sign-Rank ⋮ Query-to-Communication Lifting for BPP ⋮ On derandomized composition of Boolean functions ⋮ Nondeterministic and randomized Boolean hierarchies in communication complexity ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Probabilistic communication complexity
• Boolean function complexity. Advances and frontiers.
• Relativized Arthur-Merlin versus Merlin-Arthur games
• Expressing combinatorial optimization problems by linear programs
• Perceptrons, PP, and the polynomial hierarchy
• The landscape of communication complexity classes
• Complexity measures and decision tree complexity: a survey.
• PP is closed under intersection
• Top-down lower bounds for depth-three circuits
• Separation of the monotone NC hierarchy
• Pseudorandomness
• 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
• On the unique satisfiability problem
• Separating and collapsing results on the relativized probabilistic polynomial-time hierarchy
• Deterministic Communication vs. Partition Number
• Structure of Protocols for XOR Functions
• Lower Bounds for Elimination via Weak Regularity
• Fractional Covers and Communication Complexity
• Communication Complexity
• Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
• Strongly exponential lower bounds for monotone computation
• Communication Complexity
• Rectangles Are Nonnegative Juntas

This page was built for publication: Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)