The Pattern Matrix Method
From MaRDI portal
Publication:3225179
DOI10.1137/080733644zbMath1234.68122OpenAlexW2077740213MaRDI QIDQ3225179
Publication date: 15 March 2012
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/080733644
discrepancyapproximate ranklinear programming dualityquantum communication complexitypattern matrix methodapproximate trace normapproximation and sign-representation of Boolean functions by real polynomialsbounded-error communication complexitydegree/discrepancy theorem
Quantum computation (81P68) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (47)
Hellinger volume and number-on-the-forehead communication complexity ⋮ Hardness Amplification and the Approximate Degree of Constant-Depth Circuits ⋮ Amplification of One-Way Information Complexity via Codes and Noise Sensitivity ⋮ Approximate Degree in Classical and Quantum Computing ⋮ Communication Lower Bounds via Critical Block Sensitivity ⋮ Breaking the Minsky--Papert Barrier for Constant-Depth Circuits ⋮ The landscape of communication complexity classes ⋮ Deterministic Communication vs. Partition Number ⋮ A Short List of Equalities Induces Large Sign-Rank ⋮ Around the log-rank conjecture ⋮ Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\) ⋮ Bounds on oblivious multiparty quantum communication complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Structure of Protocols for XOR Functions ⋮ Query-to-Communication Lifting for BPP ⋮ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ On the Power of Statistical Zero Knowledge ⋮ Unnamed Item ⋮ Extension Complexity of Independent Set Polytopes ⋮ Dimension-free bounds and structural results in communication complexity ⋮ Unnamed Item ⋮ Algorithmic Polynomials ⋮ Unnamed Item ⋮ Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-bounds, and Separations ⋮ The hardest halfspace ⋮ Optimal bounds for sign-representing the intersection of two halfspaces by polynomials ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Simulation theorems via pseudo-random properties ⋮ On derandomized composition of Boolean functions ⋮ Rectangles Are Nonnegative Juntas ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ The Multiparty Communication Complexity of Set Disjointness ⋮ Lifting Theorems for Equality ⋮ Query-To-Communication Lifting for BPP Using Inner Product ⋮ Sign rank vs discrepancy ⋮ Bounded Indistinguishability and the Complexity of Recovering Secrets ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs ⋮ Communication Lower Bounds Using Directional Derivatives ⋮ Query-to-Communication Lifting Using Low-Discrepancy Gadgets ⋮ Unnamed Item ⋮ Dual lower bounds for approximate degree and Markov-Bernstein inequalities
This page was built for publication: The Pattern Matrix Method
