Communication Lower Bounds via Critical Block Sensitivity
From MaRDI portal
Publication:4554052
DOI10.1137/16M1082007zbMath1402.68074WikidataQ129070818 ScholiaQ129070818MaRDI QIDQ4554052
Publication date: 7 November 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)
Related Items
Space characterizations of complexity measures and size-space trade-offs in propositional proof systems, Unnamed Item, Query-To-Communication Lifting for BPP Using Inner Product, Unnamed Item, Query-to-Communication Lifting Using Low-Discrepancy Gadgets, Large clique is hard on average for resolution
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An information statistics approach to data stream and communication complexity
- Boolean function complexity. Advances and frontiers.
- Towards optimal simulations of formulas by bounded-width programs
- Probabilistic encryption
- Ramanujan graphs
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- A simple lower bound for monotone clique using a communication game
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- On the distributional complexity of disjointness
- An observation on time-storage trade off
- The electrical resistance of a graph captures its commute and cover times
- A characterization of span program size and improved lower bounds for monotone span programs
- Complexity measures and decision tree complexity: a survey.
- Separation of the monotone NC hierarchy
- Quadratic residues and non-residues in arithmetic progression
- Edmonds polytopes and a hierarchy of combinatorial problems
- Edge-Disjoint Paths in Expander Graphs
- A minimal model for secure computation (extended abstract)
- The NOF Multiparty Communication Complexity of Composed Functions
- Pebble Games, Proof Complexity, and Time-Space Trade-offs
- Hardness amplification in proof complexity
- Lower Bounds on the Size of Semidefinite Programming Relaxations
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- The Pattern Matrix Method
- Outline of an algorithm for integer solutions to linear programs
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
- On the Tightness of the Buhrman-Cleve-Wigderson Simulation
- Hard examples for resolution
- Cones of Matrices and Set-Functions and 0–1 Optimization
- The Probabilistic Communication Complexity of Set Intersection
- Monotone circuits for matching require linear depth
- Short proofs are narrow—resolution made simple
- Communication Complexity of Simultaneous Messages
- Optimal Construction of Edge-Disjoint Paths in Random Regular Graphs
- Search Problems in the Decision Tree Model
- Communication Complexity
- Strongly exponential lower bounds for monotone computation
- Integrality gaps for Sherali-Adams relaxations
- CSP gaps and reductions in the lasserre hierarchy
- Communication lower bounds via critical block sensitivity
- Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness
- Integrality Gaps of $2-o(1)$ for Vertex Cover SDPs in the Lovász–Schrijver Hierarchy
- Time-space tradeoffs in resolution
- On the virtue of succinct proofs
- Tight bounds for monotone switching networks via fourier analysis
- Some trade-off results for polynomial calculus
- Communication lower bounds using directional derivatives
- Approximability and proof complexity
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- Complexity of Null- and Positivstellensatz proofs
