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