Communication lower bounds via critical block sensitivity

DOI10.1137/16M1082007zbMATH Open1402.68074WikidataQ129070818 ScholiaQ129070818MaRDI QIDQ4554052FDOQ4554052

Authors: Mika Göös, Toniann Pitassi 

Publication date: 7 November 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Recommendations

• Communication lower bounds via critical block sensitivity
• A simple lower bound for monotone clique using a communication game
• Monotone circuit lower bounds from resolution
• Lower bounds for monotone real circuit depth and formula size and tree-like cutting planes
• Combinatorics of monotone computations

zbMATH Keywords

complexity theoryproof complexitycommunication complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity of proofs (03F20)

Cites Work

• Probabilistic encryption
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Outline of an algorithm for integer solutions to linear programs
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Ramanujan graphs
• Hard examples for resolution
• The Probabilistic Communication Complexity of Set Intersection
• Communication Complexity
• Boolean function complexity. Advances and frontiers.
• An observation on time-storage trade off
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• The pattern matrix method
• Communication lower bounds using directional derivatives
• An information statistics approach to data stream and communication complexity
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• Title not available (Why is that?)
• Integrality gaps for Sherali-Adams relaxations
• Edmonds polytopes and a hierarchy of combinatorial problems
• Complexity measures and decision tree complexity: a survey.
• Title not available (Why is that?)
• Short proofs are narrow—resolution made simple
• On the distributional complexity of disjointness
• A minimal model for secure computation (extended abstract)
• Lower bounds on the size of semidefinite programming relaxations
• Asymptotically optimal lower bounds on the NIH-multi-party information complexity of the AND-function and disjointness
• The electrical resistance of a graph captures its commute and cover times
• Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
• A simple lower bound for monotone clique using a communication game
• Monotone circuits for matching require linear depth
• Communication Complexity of Simultaneous Messages
• Hardness amplification in proof complexity
• Integrality gaps of \(2-o(1)\) for vertex cover SDPs in the Lovász-Schrijver hierarchy
• The NOF multiparty communication complexity of composed functions
• On the tightness of the Buhrman-Cleve-Wigderson simulation
• Separation of the monotone NC hierarchy
• Search Problems in the Decision Tree Model
• A characterization of span program size and improved lower bounds for monotone span programs
• Title not available (Why is that?)
• Towards optimal simulations of formulas by bounded-width programs
• CSP gaps and reductions in the lasserre hierarchy
• Communication lower bounds via critical block sensitivity
• Title not available (Why is that?)
• Tight bounds for monotone switching networks via Fourier analysis
• Edge-disjoint paths in expander graphs
• Title not available (Why is that?)
• Complexity of Null- and Positivstellensatz proofs
• Simplified lower bounds on the multiparty communication complexity of disjointness
• Strongly exponential lower bounds for monotone computation
• Pebble games, proof complexity, and time-space trade-offs
• Some trade-off results for polynomial calculus (extended abstract)
• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
• Approximability and proof complexity
• Optimal Construction of Edge-Disjoint Paths in Random Regular Graphs
• Quadratic residues and non-residues in arithmetic progression
• Time-space tradeoffs in resolution, superpolynomial lower bounds for superlinear space
• On the virtue of succinct proofs

Cited In (11)

• Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
• Computationally efficient block transmission systems with and without guard periods
• Large clique is hard on average for resolution
• Communication lower bounds via critical block sensitivity
• Communication lower bounds using directional derivatives
• Monotone circuit lower bounds from resolution
• High-threshold AVSS with optimal communication complexity
• Query-to-communication lifting using low-discrepancy gadgets
• Cutting planes width and the complexity of graph isomorphism refutations
• Title not available (Why is that?)
• Query-to-communication lifting for BPP using inner product

This page was built for publication: Communication lower bounds via critical block sensitivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4554052)