Communication Lower Bounds via Critical Block Sensitivity
type: Item
instance of: scholarly article
title: Communication Lower Bounds via Critical Block Sensitivity
zbMATH Open document ID: 1402.68074
DOI: 10.1137/16M1082007
author: Mika Göös
author: Toniann Pitassi
published in: SIAM Journal on Computing
publication date: 2018-11-07T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 68Q10
zbMATH DE Number: 6974482
zbMATH Keywords: complexity theory
zbMATH Keywords: communication complexity
zbMATH Keywords: proof complexity
MaRDI profile type: Publication
cites work: The NOF Multiparty Communication Complexity of Composed Functions
cites work: Communication Complexity of Simultaneous Messages
cites work: Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
cites work: An information statistics approach to data stream and communication complexity
cites work: Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
cites work: Time-space tradeoffs in resolution
cites work: Hardness amplification in proof complexity
cites work: Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
cites work: Some trade-off results for polynomial calculus
cites work: Short proofs are narrow—resolution made simple
cites work: Complexity measures and decision tree complexity: a survey.
cites work: Tight bounds for monotone switching networks via fourier analysis
cites work: Approximate Constraint Satisfaction Requires Large LP Relaxations
cites work: The electrical resistance of a graph captures its commute and cover times
cites work: Integrality gaps for Sherali-Adams relaxations
cites work: Edmonds polytopes and a hierarchy of combinatorial problems
cites work: Towards optimal simulations of formulas by bounded-width programs
cites work: An observation on time-storage trade off
cites work: Q4434901
cites work: A minimal model for secure computation (extended abstract)
cites work: Edge-disjoint paths in expander graphs
cites work: Optimal Construction of Edge-Disjoint Paths in Random Regular Graphs
cites work: A characterization of span program size and improved lower bounds for monotone span programs
cites work: Q4601841
cites work: Integrality Gaps of $2-o(1)$ for Vertex Cover SDPs in the Lovász–Schrijver Hierarchy
cites work: A simple lower bound for monotone clique using a communication game
cites work: Probabilistic encryption
cites work: Outline of an algorithm for integer solutions to linear programs
cites work: Communication lower bounds via critical block sensitivity
cites work: Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
cites work: Complexity of Null- and Positivstellensatz proofs
cites work: Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness
cites work: On the virtue of succinct proofs
cites work: Boolean function complexity. Advances and frontiers.
cites work: The Probabilistic Communication Complexity of Set Intersection
cites work: Monotone Circuits for Connectivity Require Super-Logarithmic Depth
cites work: Communication Complexity
cites work: Q4537750
cites work: Lower Bounds on the Size of Semidefinite Programming Relaxations
cites work: Search Problems in the Decision Tree Model
cites work: Cones of Matrices and Set-Functions and 0–1 Optimization
cites work: Ramanujan graphs
cites work: Q5655273
cites work: Pebble games, proof complexity, and time-space trade-offs
cites work: Approximability and proof complexity
cites work: Q4385520
cites work: Strongly exponential lower bounds for monotone computation
cites work: Q4601824
cites work: Separation of the monotone NC hierarchy
cites work: Monotone circuits for matching require linear depth
cites work: On the distributional complexity of disjointness
cites work: A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
cites work: The Pattern Matrix Method
cites work: Communication lower bounds using directional derivatives
cites work: CSP gaps and reductions in the lasserre hierarchy
cites work: Hard examples for resolution
cites work: Quadratic residues and non-residues in arithmetic progression
cites work: On the Tightness of the Buhrman-Cleve-Wigderson Simulation
Wikidata QID: Q129070818
description: scientific article; zbMATH DE number 6974482