The Pattern Matrix Method
From MaRDI portal
Publication:3225179
DOI10.1137/080733644zbMath1234.68122MaRDI 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
discrepancy; approximate rank; linear programming duality; quantum communication complexity; pattern matrix method; approximate trace norm; approximation and sign-representation of Boolean functions by real polynomials; bounded-error communication complexity; degree/discrepancy theorem
81P68: Quantum computation
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Unnamed Item, Communication Lower Bounds via Critical Block Sensitivity, Breaking the Minsky--Papert Barrier for Constant-Depth Circuits, Deterministic Communication vs. Partition Number, Structure of Protocols for XOR Functions, Extension Complexity of Independent Set Polytopes, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$, Unnamed Item, Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs, Unnamed Item, Approximate Degree in Classical and Quantum Computing, A Short List of Equalities Induces Large Sign-Rank, 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, Algorithmic Polynomials, Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-bounds, and Separations, Lifting Theorems for Equality, Query-To-Communication Lifting for BPP Using Inner Product, Sign rank vs discrepancy, Communication Lower Bounds Using Directional Derivatives, Unnamed Item, Unnamed Item, Optimal bounds for sign-representing the intersection of two halfspaces by polynomials, Rectangles Are Nonnegative Juntas, Query-to-Communication Lifting Using Low-Discrepancy Gadgets, Around the log-rank conjecture, Bounds on oblivious multiparty quantum communication complexity, Hellinger volume and number-on-the-forehead communication complexity, The landscape of communication complexity classes, The hardest halfspace, Simulation theorems via pseudo-random properties, On derandomized composition of Boolean functions, Dual lower bounds for approximate degree and Markov-Bernstein inequalities, Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\), Dimension-free bounds and structural results in communication complexity, Unnamed Item, Unnamed Item, The Multiparty Communication Complexity of Set Disjointness, Bounded Indistinguishability and the Complexity of Recovering Secrets, Hardness Amplification and the Approximate Degree of Constant-Depth Circuits, Amplification of One-Way Information Complexity via Codes and Noise Sensitivity
